One-to-all Shortest Paths

= length of the shortest path from x to y.
= 0; if y is unreachable from x.

BFS generalized:

BFS would work if w(e) = 1.

Optimal Substructure:

Subpaths of shortest paths are shortest paths.

Triangle Inequality:

.

Negatively-weighted Cycles:

Some shortest paths may be undefined.

• Bellman-Ford Algorithm
• DIJKSTRA's ALGORITHM