Family: Graph
Find the shortest distance and shortest path to get from Origin node to any reachable node on a weighted graph.
Dijkstra's algorithm can also be used to determine shortest path to get from Origin to Destination node.
Eagerly, for each unvisited node, determine the shortest accumulated distance and the previous node in the most optimal path to get to that node from Origin node.
To determine the shortest path to get to Destination node, walk back from Destination node's previous node until you reach Origin node, and reverse that path.
O(E*Log(V))
where E is the number of edges, and V is the number of vertices.
- Maps Navigation
- Network Routing
Google Maps: Innovation or Old News? - Post by Ibrahim Zananiri