Dijkstra's algorithm

Dijkstra's algorithm finds single-source shortest paths in a directed graph with non-negative edge weights. (When negative-weight edges are allowed, the Bellman–Ford algorithm must be used instead.) It is the algorithm of choice for solving this problem, because it is easy to understand, relatively easy to code, and, so far, the fastest algorithm known for solving this problem in the general case. In sparse graphs, running it once on every vertex to generate all-pairs shortest paths is faster than solving the same problem with the Floyd–Warshall algorithm. (The precise time complexity of Dijkstra's depends on the nature of the data structures used; read on.)

Theory of the algorithm

Dijkstra's may be characterized as a greedy algorithm, which builds the shortest-paths tree one edge at a time, adding vertices in non-decreasing order of their distance from the source. That is, in each step of the algorithm, we will find the next-closest vertex to the source. (If there is a tie, it does not matter which one is chosen.)

Lemma 1

Suppose that the distances from the source to the $k$ closest vertices ($0 < k < V$) are known, where this set of $k$ vertices is denoted by $T$. (If there is a tie, it does not matter which vertices are chosen.) Then, some shortest path to any vertex not in $T$ consists of zero or more edges from $T$ to itself followed by a single edge that leads out of $T$.

Proof: Suppose we have a path from the source s to some vertex v not in $T$. Then, the first vertex in the path is s, and it is folloewd by zero or more edges that lead from $T$ to itself. At some point there must be an edge leading out of $T$ to some vertex u. This sequence of edges constituting a path from s to $T$ is at least as short as the whole path, since all edges have non-negative weights. So any path that does not consist of one or more edges from $T$ to itself followed by a single edge out of $T$ either exceeds or equals in length a path that does satisfy the property, and hence the original path does not need to be considered if we seek the next closest vertex from the source.

The algorithm

The preceding Lemma should give us an idea of how to proceed. We start with only the source vertex in the shortest-paths tree; its distance to itself is obviously zero. Then, we repeatedly apply the Lemma: we consider all outgoing edges u-v of vertices in $T$; each one induces a possible shortest path from the source s to v when the u-v edge is appended to the shortest s-u path (already known).