Shortest Path
Overview
https://www.youtube.com/watch?v=HXINXtriDQc&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E&index=9
TRC PowerPoints
Dijkstra
The shortest path is usually found by Dijkstra's algorithm. The algorithm functions as follows:
Step 1 Give the permanent label 0 to the starting vertex.
Step 2 Give temporary labels to each vertex that is connected directly to the starting vertex.
Step 3 Find the vertex with the smallest temporary label, number it and make it permanent.
Step 4 Give temporary labels to each vertex that is connected directly to the previous vertex. Then find the vertex with the smallest temporary label, number it and make it permanent.
Step 5 Repeat Step 4 until you have given a permanent label to the finishing vertex.
Step 6 Use the permanent labels to trace back through the network to find the shortest path.
Step 7 The shortest path is found by tracing back in such a way that an edge is only included if its distance equals the change in label values.
Example
This is the starting graph and values:
The stages to identify the shortest path from St. Austell to Launceston:
Further Example
