Match the shortest-path algorithm to edge assumptions
Dijkstra requires nonnegative edge weights. Bellman-Ford permits negative edges and detects a negative cycle reachable from the source. Floyd-Warshall computes all-pairs distances using an O(V³) dynamic program and O(V²) storage.
A -> B costs 4
A -> C costs 1
C -> B costs 2
Dijkstra first settles A, then C at distance one, then B at distance three after relaxation through C. A priority-queue implementation should skip stale entries when a shorter distance has since been recorded.
Bellman-Ford relaxes every edge up to V-1 times; an additional improvement signals a reachable negative cycle. Floyd-Warshall considers each vertex as a permitted intermediate point, with that intermediate loop outermost. Never add an “infinity” sentinel blindly: unreachable distances and integer overflow need explicit handling.
Exercise
Implement Dijkstra for a nonnegative adjacency list and compare it with Bellman-Ford on small generated graphs. Add an unreachable vertex and a zero-weight edge. Reject negative edges in the Dijkstra input contract.
Check: a negative cycle matters only for paths that can reach it and continue to the destination under consideration; it does not automatically invalidate every disconnected part of the graph.