Loading...
Dijkstra's algorithm finds shortest path distances from a single source in a weighted graph with non‑negative edges using a greedy frontier guided by a priority queue that always settles the closest tentative vertex.
Choose nearest unsettled
Min-distance ordering
Improve tentative paths
Maintain a set of settled vertices whose distances are finalized. Keep a priority queue of frontier vertices keyed by tentative dist. Extract the minimum, settle it, and relax all outgoing edges—updating neighbors' tentative distances if a shorter path is found. Non‑negative weights guarantee greedy correctness: once extracted, a vertex cannot later receive a shorter path.