Difference between revisions of "Shortest Path"
| Line 6: | Line 6: | ||
# The previous 2 steps are repeated: the distance to the each unlocked node connected to a locked node is noted and the closest node to the start is selected (regardless of when the distance was given). | # The previous 2 steps are repeated: the distance to the each unlocked node connected to a locked node is noted and the closest node to the start is selected (regardless of when the distance was given). | ||
# 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. | # 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. | ||
| + | #When every node is marked, the shortest path can be calculated by working backwards. From the shortest distance to the final node, subtract the weights of the connecting arcs. If the value is equal to shortest distance the connected node, it is part of the shortest path. It is possible for multiple shortest paths to exist. | ||
[[File:Dijkstra.png|thumb]] | [[File:Dijkstra.png|thumb]] | ||
Revision as of 11:19, 22 May 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 unlocked node that is connected directly to a locked node by a weighted arc is given a temporary label, equal to the total weight to reach it (from the starting node) if the new distance is less then any previously marked.
- The node closest to the start is locked in with the shortest distance available and marked as the next node in the path.
- The previous 2 steps are repeated: the distance to the each unlocked node connected to a locked node is noted and the closest node to the start is selected (regardless of when the distance was given).
- 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.
- When every node is marked, the shortest path can be calculated by working backwards. From the shortest distance to the final node, subtract the weights of the connecting arcs. If the value is equal to shortest distance the connected node, it is part of the shortest path. It is possible for multiple shortest paths to exist.
