Dijkstra's algorithm - Revision history

Brian at 05:45, 31 May 2011

2011-05-31T05:45:31Z

Brian at 07:01, 26 May 2011

2011-05-26T07:01:18Z

Brian at 06:27, 24 May 2011

2011-05-24T06:27:00Z

Brian at 20:01, 15 November 2010

2010-11-15T20:01:49Z

Brian: /* References */

2009-12-23T18:26:46Z

‎References

Brian at 18:26, 23 December 2009

2009-12-23T18:26:24Z

Brian: /* The algorithm */

2009-12-23T18:22:25Z

‎The algorithm

Jargon: categorize

2009-12-23T17:18:32Z

categorize

Brian: /* Implementation */

2009-12-20T18:05:00Z

‎Implementation

Brian at 01:56, 19 December 2009

2009-12-19T01:56:58Z

← Older revision		Revision as of 05:45, 31 May 2011
Line 75:		Line 75:

	[[Category:Algorithms]]		[[Category:Algorithms]]
		+	[[Category:Graph theory]]

@@ Line 26: / Line 26: @@
            dist[w] = min(dist[w],dist[v]+wt(v,w))
 </pre>
 ===Analysis===
@@ Line 51: / Line 52: @@
 Using a [[Fibonacci heap]] implementation, which supports amortized constant time insertion, we can improve this to <math>O(E + V \log V)</math>.
 ==References==

@@ Line 12: / Line 12: @@
 The preceding Lemma should give us an idea of how to proceed. We start with only the source vertex in the shortest-paths tree (<math>T</math> is merely the vertex set of the partial shortest-paths tree); its distance to itself is obviously zero. Then, we repeatedly apply the Lemma by considering all admissible paths and finding the shortest. To do this we consider all edges that lead from a <math>T</math> vertex <i>u</i> to a non-<math>T</math> vertex <i>v</i>. Concatenating the <i>s</i>-<i>u</i> shortest path and the <i>u</i>-<i>v</i> edge yields an admissible path whose length is the sum of the length of the already-known <i>s</i>-<i>u</i> path and the weight of the <i>u</i>-<i>v</i> edge. The edge and vertex <i>v</i> at the very end of the shortest admissible path are added to the shortest-paths tree (and thus <i>v</i> is added to <math>T</math>); as no path from <i>s</i> to a non-<math>T</math> vertex can be shorter, we are justified in claiming that <i>v</i> is the closest non-<math>T</math> vertex to <i>s</i>, and that its distance from <i>s</i> is the shortest obtainable from an admissible path currently. This method of extending the shortest-paths tree by one vertex is repeated until all vertices have been added, and induction proves the algorithm's validity. (The extension can always be performed because otherwise the remaining vertices would be unreachable from the source, a contradiction.)
-==Implementation==
+==Implementation 1==
 As the previous sections are a bit heavy, here is some pseudocode for Dijkstra's algorithm:
 <pre>
@@ Line 26: / Line 26: @@
            dist[w] = min(dist[w],dist[v]+wt(v,w))
 </pre>
 ==References==

@@ Line 1: / Line 1: @@
-'''Dijkstra's algorithm''' finds [[Shortest path|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.)
+'''Dijkstra's algorithm''' finds [[Shortest_path#Single-source_shortest_paths|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=
+==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. (If you find the two sections below too difficult, skip them.)
-==Lemma==
+===Lemma===
-<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>
+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>''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>
+''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.
-==The algorithm==
+===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 (<math>T</math> is merely the vertex set of the partial shortest-paths tree); its distance to itself is obviously zero. Then, we repeatedly apply the Lemma by considering all admissible paths and finding the shortest. To do this we consider all edges that lead from a <math>T</math> vertex <i>u</i> to a non-<math>T</math> vertex <i>v</i>. Concatenating the <i>s</i>-<i>u</i> shortest path and the <i>u</i>-<i>v</i> edge yields an admissible path whose length is the sum of the length of the already-known <i>s</i>-<i>u</i> path and the weight of the <i>u</i>-<i>v</i> edge. The edge and vertex <i>v</i> at the very end of the shortest admissible path are added to the shortest-paths tree (and thus <i>v</i> is added to <math>T</math>); as no path from <i>s</i> to a non-<math>T</math> vertex can be shorter, we are justified in claiming that <i>v</i> is the closest non-<math>T</math> vertex to <i>s</i>, and that its distance from <i>s</i> is the shortest obtainable from an admissible path currently. This method of extending the shortest-paths tree by one vertex is repeated until all vertices have been added, and induction proves the algorithm's validity. (The extension can always be performed because otherwise the remaining vertices would be unreachable from the source, a contradiction.)
-=Implementation=
+==Implementation==
 As the previous sections are a bit heavy, here is some pseudocode for Dijkstra's algorithm:
 <pre>
@@ Line 27: / Line 27: @@
 </pre>
-=References=
+==References==
 * Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". ''Introduction to Algorithms'' (Second ed.). MIT Press and McGraw-Hill. pp. 595–601. ISBN 0-262-03293-7.
 [[Category:Algorithms]]

@@ Line 28: / Line 28: @@
 =References=
-Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". ''Introduction to Algorithms'' (Second ed.). MIT Press and McGraw-Hill. pp. 595–601. ISBN 0-262-03293-7.
+* Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". ''Introduction to Algorithms'' (Second ed.). MIT Press and McGraw-Hill. pp. 595–601. ISBN 0-262-03293-7.
 [[Category:Algorithms]]

← Older revision		Revision as of 17:18, 23 December 2009
Line 26:		Line 26:
	dist[w] = min(dist[w],dist[v]+wt(v,w))		dist[w] = min(dist[w],dist[v]+wt(v,w))
	</pre>		</pre>
		+
		+	[[Category:Algorithms]]

@@ Line 19: / Line 19: @@
       let dist[v] = ∞
 let dist[s] = 0
-let T be empty
+let T = ∅
 while T ≠ V(G)
       let v ∈ V(G)\T such that dist[v] is minimal