Shortest distance

A reasonable question to have about a weighted graph is ``what's the shortest distance from A to B?'' (assuming that A and B are nodes on this graph). Translating the question into graph theory, this means that if $G$ is a weighted graph with vertices $u$ and $v$, we want to know which path from $u$ to $v$ has the minimum cumulative weight (minimum sum of edge weights in the path). For example, if $G$ were a weighted graph representing cities in southern Ontario and Quebec, with the weights being road distances between cities, then it would be reasonable to ask what the shortest distance from Toronto to Montreal is (probably not taking the QEW to Hamilton, the 403 to London, and then the 401 to Montreal).

Some conditions need to be set. Although we may be able to tolerate negative weights on some edges of $G$, negative cycles (even a cycle with only 2 vertices) are not allowed (or else there would be no minimum!). Notice that this means that any undirected graph with a negative weight, say $w(i,j) = -1$, has a negative cycle (you can step back and forth from $i$ to $j$ and pick up a negative one each time).

Here's an algorithm that works for non-negative weights, by Edgster Dijkstra: