Shortest Path

Overview

https://www.youtube.com/watch?v=HXINXtriDQc&list=PLCiOXwirraUB0HOYmEbmx-7KStKtoXZ6E&index=9

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