Dijkstra’s algorithm
A.k.a “Shortest Path First” (SPF) algorithm.
Idea: compute shortest path from a “root” node to every other node.“Greedy method”:
- P is a set of nodes for which shortest path has already been found.
- For every node “o” outside P, find shortest one-hop path from some node in P.
- Add that node “o” which has the shortest of these paths to P. Record the path found.
- Continue till we add all nodes (&paths) to P