Editing Dijkstra's algorithm
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
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.) | 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: | As the previous sections are a bit heavy, here is some pseudocode for Dijkstra's algorithm: | ||
<pre> | <pre> | ||
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> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==References== | ==References== | ||
Line 75: | Line 31: | ||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
− |