“Create a top-down Dijkstra shortest-path algorithm flowchart: read a non-negative weighted graph and source s, set the source distance to 0 and all other distances to infinity, then repeatedly select the unvisited vertex with minimum distance, relax its outgoing edges, and mark it visited. Leave vertices whose distance remains infinity marked unreachable, output shortest distances and predecessors, and end.”
Die dahinterstehenden Entscheidungen verstehen.
The graph requirement is stated at input because Dijkstra's algorithm is not correct with negative edge weights.
Only the source starts at zero; all other tentative distances begin at infinity.
Each iteration chooses the unvisited vertex with the smallest known tentative distance.
Vertices still at infinity are explicitly reported as unreachable rather than assigned a false path.
Use this for single-source shortest paths with non-negative weights. Choose Bellman-Ford or another suitable algorithm when negative edges are possible.
Häufige Fragen
Why must weights be non-negative?
Dijkstra's greedy minimum-distance selection is not reliable when a later negative edge can reduce a finalized distance.
What does relaxing an edge mean?
It means updating a neighbor's tentative distance and predecessor if going through the current vertex is shorter.
How are unreachable vertices represented?
Their distance remains infinity and the flow marks them unreachable before output.