(* the above algorithm is from the book "Data Structures and Algorithms in Java", 6th Edition, By: Michael T. Goodrich; Roberto Tamassia, John Wiley & Sons)
Find shortest paths (using Dijkstra's Algorithm) for the following graph, start vertex is BWI.
|
|
|||||||||||
| Action | Cloud | Priority Queue | JFK | MIA | BOS | DFW | PVD | SFO | LAX | ORD | |
| { } | [ (0, BWI), (inf, JFK), (inf,ORD), (inf, MIA), (inf, DFW), (inf, BOS), (inf, PVD), (inf, SFO), (inf, LAX) ] | . | . | . | . | . | . | . | . | ||
| pull BWI into the cloud | + BWI (0) | [ (184, JFK), (621,ORD), (946, MIA), (inf, DFW), (inf, BOS), (inf, PVD), (inf, SFO), (inf, LAX) ] | BWI | BWI | . | . | . | . | . | BWI | |
| pull JFK into the cloud | + JFK (184) | [ (328, PVD), (371, BOS), (621, ORD), (946, MIA), (1575, DFW), (inf, SFO), (inf, LAX) ] | BWI | BWI | JFK | JFK | JFK | . | . | BWI | |
| pull PVD | + PVD (328) | [ (371, BOS), (621, ORD), (946, MIA), (1575, DFW), (inf, SFO), (inf, LAX) ] | BWI | BWI | JFK | JFK | JFK | . | . | BWI | |
| pull BOS | + BOS (371) | [ (621, ORD), (946, MIA), (1575, DFW), (3075, SFO), (inf, LAX) ] | BWI | BWI | JFK | JFK | JFK | BOS | . | BWI | |
| pull ORD,
update DFW and SFO |
+ ORD (621) | [ (946, MIA), (1423, DFW), (2467, SFO), (inf, LAX) ] | BWI | BWI | JFK | ORD | JFK | ORD | . | BWI | |
| pull MIA | + MIA (946) | [ (1423, DFW), (2467, SFO), (3288, LAX) ] | BWI | BWI | JFK | ORD | JFK | ORD | MIA | BWI | |
| pull DFW,
update LAX |
+ DFW (1423) | [ (2467, SFO), (2658, LAX) ] | BWI | BWI | JFK | ORD | JFK | ORD | DFW | BWI | |
| pull SFO | + SFO (2467) | [ (2658, LAX) ] | BWI | BWI | JFK | ORD | JFK | ORD | DFW | BWI | |
| pull LAX | + LAX (2658) | [ ] | BWI | BWI | JFK | ORD | JFK | ORD | DFW | BWI | |
To recover the path itself, trace back through the Predecessor table. E.g., the shortest path to LAX goes through (in reverse order) LAX, DFW, ORD, BWI.
(*The above example is from the book "Data Structures and Algorithms in Java", 6th Edition, By: Michael T. Goodrich; Roberto Tamassia, John Wiley & Sons)