Difference between revisions of "Dijkstra's algorithm"
(Created page with ''''Dijkstra's algorithm''' finds single-source shortest paths in a directed graph with non-negative edge weights. (When negative-weight edges are allowed, the […') |
|||
| Line 2: | Line 2: | ||
=Theory of the algorithm= | =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.) | + | 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.) We assume below that all nodes are reachable from the source. |
| − | ==Lemma | + | ==Lemma== |
| − | <p>Suppose that | + | <p>Suppose that we are given a set <math>T</math> of vertices, containing the source <i>s</i>. We shall call a path <i>admissible</i> if it starts at <i>s</i>, proceeds through a sequence of vertices contained within <math>T</math>, and ends with a single non-<math>T</math> vertex. We claim that there exists an admissible path such that no other path from <i>s</i> to a non-<math>T</math> vertex is shorter.</p> |
| − | <p>''Proof'': | + | <p>''Proof'': This consists of nothing but a series of observations. First, any path from <i>s</i> to a vertex <i>v</i> outside <math>T</math> contains at least one edge from a vertex in <math>T</math> to one outside, since <i>s</i> ∈ <math>T</math>. Second, if the first such edge encountered along the path from <i>s</i> is not the last edge in the path, we can "cut off" the path at that point to obtain a path from <i>s</i> out of <math>T</math> that is not longer (since all edges have non-negative weights). Third, if the sub-path from <i>s</i> to the last vertex in <math>T</math>, denoted <i>u</i>, is not itself a shortest path from <i>s</i> to <i>u</i>, the length of the whole path may be decreased by substituting a shortest path from <i>s</i> to <i>u</i> for the current one. Now, suppose the opposite of what we want to prove: the shortest path from <i>s</i> out of <math>T</math>, or all the shortest paths from <i>s</i> out of <math>T</math>, is/are inadmissible. Then we may construct an admissible path using the three observations above which is not longer, a contradiction.</p> |
==The algorithm== | ==The algorithm== | ||
Revision as of 01:18, 19 December 2009
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.) We assume below that all nodes are reachable from the source.
Lemma
Suppose that we are given a set 
of vertices, containing the source s. We shall call a path admissible if it starts at s, proceeds through a sequence of vertices contained within , and ends with a single non- vertex. We claim that there exists an admissible path such that no other path from s to a non- vertex is shorter.
Proof: This consists of nothing but a series of observations. First, any path from s to a vertex v outside contains at least one edge from a vertex in to one outside, since s ∈ . Second, if the first such edge encountered along the path from s is not the last edge in the path, we can "cut off" the path at that point to obtain a path from s out of that is not longer (since all edges have non-negative weights). Third, if the sub-path from s to the last vertex in , denoted u, is not itself a shortest path from s to u, the length of the whole path may be decreased by substituting a shortest path from s to u for the current one. Now, suppose the opposite of what we want to prove: the shortest path from s out of , or all the shortest paths from s out of , is/are inadmissible. Then we may construct an admissible path using the three observations above which is not longer, a contradiction.
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 ; 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).
