Dijkstra’s Algorithm

Dijkstra’s Algorithm is a type of Shortest Path Algorithm that is used to find the shortest path from the source vertex to every other vertex in the graph.

Algorithm of Dijkstra's

1] Let the distance of all other vertices from start = $\infty$ (infinity)

2] Repeat

• Visit the unvisited vertex with the smallest known distance from the start vertex.

• For the current vertex, examine its unvisited neighbors.

• For the current vertex, calculate the distance of each neighbor from the start vertex.

• If the calculated distance of a vertex is less than the known distance, update the shortest distance.

• Update the previous vertex for each of the updated distances.

• Add the current vertex to the list of visited vertices.

Until all vertices are visited.

Let's apply Dijkstra's Algorithm on the given graph, to find the shortest path from the source vertex 0 to every other vertex in the graph.

Step 1 –

• Consider the start vertex = 0
• Distance from Vertex 0 to Vertex 0 is 0.
• Distances to all other vertices from a Vertex 0 are unknown initially, therefore put it as $\infty$ (infinity).

At start list of visited and unvisited vertices are as follows:

Visited Vertices = { }

Unvisited Vertices = {0, 1, 2, 3, 4, 5, 6, 7, 8}

Step 2 –

• First time around, visit the start vertex 0
• For the current vertex 0, examine its unvisited neighbors therefore, for current vertex 0 its unvisited neighbors are 1 and 7.
• Calculate the distance of each neighbor from the start vertex.
• As here we calculated distance the first time only hence just update the shortest distance.
• In this case, we visited Vertices 1 and 7 via vertex 0 and update the previous vertex for each of the updated distances.
• Add the current vertex 0 to the list of visited vertices.

Therefore,

Visited Vertices = {0}

Unvisited Vertices = {1, 2, 3, 4, 5, 6, 7, 8}

Step 3 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 1 now.
• For the current vertex 1, examine its unvisited neighbors therefore, for current vertex 1 its unvisited neighbors are 2 and 7.
• Calculate the distance of each neighbor from the start vertex.
• As the calculated distance of a vertex 7 is not less than the previously known distance, therefore, there is no need to update the shortest distance for vertex 7. Update the shortest distance only for vertex 2.
• In this case, we visited Vertex 2 via vertex 1 and update the previous vertex for each of the updated distances.
• Add the current vertex 1 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1}

Unvisited Vertices = {2, 3, 4, 5, 6, 7, 8}

Step 4 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 7 now.
• For the current vertex 7, examine its unvisited neighbors therefore, for current vertex 7 its unvisited neighbors are 8 and 6.
• Calculate the distance of each neighbor from the start vertex.
• Update the calculated shortest distance of vertices 8 and 6 as it is calculated the first time only.
• In this case, we visited vertices 8 and 6 via vertex 7 and update the previous vertex for each of the updated distances.
• Add the current vertex 7 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1, 7}

Unvisited Vertices = {2, 3, 4, 5, 6, 8}

Step 5 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 6 now.
• For the current vertex 6, examine its unvisited neighbors therefore, for current vertex 6 its unvisited neighbors are 8 and 5.
• Calculate the distance of each neighbor from the start vertex.
• As the calculated distance of a vertex 8 is not less than the previously known distance, therefore, there is no need to update the shortest distance for vertex 8. Update the shortest distance only for vertex 5.
• In this case, we visited vertex 5 via vertex 6 and update the previous vertex for each of the updated distances.
• Add the current vertex 6 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1, 7, 6}

Unvisited Vertices = {2, 3, 4, 5, 8}

Step 6 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 5 now.
• For the current vertex 5, examine its unvisited neighbors therefore, for current vertex 5 its unvisited neighbors are 2, 3, and 4.
• Calculate the distance of each neighbor from the start vertex.
• Update the calculated shortest distance of vertices 3 and 4 as it is calculated the first time only.
• As the calculated distance of vertex 2 is not less than the previously known distance, therefore, there is no need to update the shortest distance for vertex 2. Update the shortest distance only for vertices 3 and 4.
• In this case, we visited vertices 3 and 4 via vertex 5 and update the previous vertex for each of the updated distances.
• Add the current vertex 5 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1, 7, 6, 5}

Unvisited Vertices = {2, 3, 4, 8}

Step 7 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 2 now.
• For the current vertex 2, examine its unvisited neighbors therefore, for current vertex 2 its unvisited neighbors are 3 and 8.
• Calculate the distance of each neighbor from the start vertex.
• As the calculated distance of vertices 8 and 3 both are less than the previously known distances, therefore, we need to update the shortest distances for vertices 8 and 3 again.
• In this case, we visited vertices 8 and 3 via 2 and update the previous vertex for each of the updated distances.
• Add the current vertex 2 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1, 7, 6, 5, 2}

Unvisited Vertices = {3, 4, 8}

Step 8 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 8 now.
• For the current vertex 8, examine its unvisited neighbors.
• But vertex 8 has no unvisited neighbors.
• Therefore, add the current vertex 8 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1, 7, 6, 5, 2, 8}

Unvisited Vertices = {3, 4}

Step 9 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 3 now.
• For the current vertex 3, examine its unvisited neighbors, for the current vertex 3 has only one unvisited neighbor that is vertex 4 only.
• Calculate distance with the neighbor vertex from the start vertex.
• As the calculated distance of vertex 4 is not less than the previously known distance, therefore, there is no need to update the shortest distance for vertex 4.
• Add the current vertex 3 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1, 7, 6, 5, 2, 8, 3}

Unvisited Vertices = {4}

Step 10 –

• Visit the unvisited vertex with the smallest known distance from the start vertex therefore it is a vertex 4 now.
• For the current vertex 4, examine its unvisited neighbors.
• But vertex 4 has no unvisited neighbors.
• Therefore, add the current vertex 4 to the list of visited vertices.

Therefore,

Visited Vertices = {0, 1, 7, 6, 5, 2, 8, 3, 4}

Unvisited Vertices = { }

Here, we calculated distances for all vertices of the given graph from source vertex 0 using Dijkstra’s Algorithm as follows:

We can also compute the shortest path from source vertex 0 to each vertex based on the previous vertex by using Backtracking methodology as follows:

Based on this we can draw Shortest Path Tree (SPT) as follows: