Difference between revisions of "Shortest Path"
m (Corrected spelling. Removed repeated title.) |
m (Fixed Link) |
||
| Line 1: | Line 1: | ||
| − | The shortest path is usually found by ''[https:// | + | The shortest path is usually found by ''[https://www.youtube.com/watch?v=gdmfOwyQlcI Dijkstra's algorithm]''. |
The algorithm functions as follows: | The algorithm functions as follows: | ||
# The first node has a distance of 0, this is locked in and labeled node one. | # The first node has a distance of 0, this is locked in and labeled node one. | ||
Revision as of 14:04, 16 January 2017
The shortest path is usually found by Dijkstra's algorithm. The algorithm functions as follows:
- The first node has a distance of 0, this is locked in and labeled node one.
- Each non locked in node that is connected by a weighted arc gains a temporary label equal to the total weight to reach it so long as the new distance is less then any previously marked.
- The lowest distance node is locked in with the shortest distance available and marked as the next node in the path.
- Each new arc available is then checked, and the second and third steps are repeated using the total distance to reach the node.
- Once every node is marked, the shortest path would be the backwards path from the last node, where taking the arc reaches the distance on the locked in node until the final number is zero at the start.
