Modified Dijkstra's algorithm in Python
Algorithm: perform a breadth-first search, always expand the vertex with the smallest cost, and don't remove duplicate vertices in the cost-priority-queue.
This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For n vertices and m edges, it requires O(n+m) space, O(m*log(m)) time, and always finds the shortest path.
The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).
This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For n vertices and m edges, it requires O(n+m) space, O(m*log(m)) time, and always finds the shortest path.
The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).
posted by Connelly Barnes at 6:32 PM
1 Comments:
That, sir, is one of the most elegant Dijkstra I've ever seen. Thanks for sharing.
Post a Comment
<< Home