Shortest Path
Shortest Path
The shortest path is usually found by Djikstra'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.
