Tarjan's implementation of Dijkstra's algorithm
Posted: Fri Dec 24, 2004 10:12 pm
Hello,
I have problem with implementation of algorithm for the shortest path in weighted graph, where complexity depends also on the maximum weight of the edges. In Cormen's 'Introduction to algorithms' I found, that Ahuja, Mehlhorn, Orlin and Tarjan described it in their 'Faster algorithms for the shortest path problem', but I can't get this book.
Specification says:
"On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C, a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O(m + n log C)."
Could anybody write me sth about this implementation or give an url of helpful web page?
I have problem with implementation of algorithm for the shortest path in weighted graph, where complexity depends also on the maximum weight of the edges. In Cormen's 'Introduction to algorithms' I found, that Ahuja, Mehlhorn, Orlin and Tarjan described it in their 'Faster algorithms for the shortest path problem', but I can't get this book.
Specification says:
"On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C, a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O(m + n log C)."
Could anybody write me sth about this implementation or give an url of helpful web page?