In this tutorial we shall learn about Dijkstra’s algorithm. It is used to get single source shortest path algorithm.

So what is single source shortest path?

You are given a weighted graph and you are given a source. You need to find shortest path from source vertex to every other vertex in the graph.

Example:

So to find the shortest path between “A” and “C”, you can reach from “A” to “C” by:

A -> E -> C = 4 + 3 = 7

A -> B -> C = 2 + 4 = 6

A -> D -> E -> C = 5 + 2 + 3 = 9

Hence the shortest path is A -> B -> C.

So to solve this, we can generate all the possible paths from the source vertex to every other vertex. Find the weight of all the paths, compare those weights and find min of all those weights. This can be optimized using Dijkstra’s algorithm.

Dijkstra’s algorithm is a greedy algorithm. The graph should have the following properties to work:

- The algorithm works on both directed and undirected graphs.
- All the edges should have positive weight.
- Graph should be connected.

Below are the steps to perform Dijkstra’s algorithm.

Step 1: Select any vertex as starting vertex.

Step 2: Make the distance for all other vertices as INF

Step 3: From the starting vertex, visit all it’s adjacent/ neighboring vertices and write their cost/value.

Step 4: Now that we have finished visiting all the adjacent vertices, we make the source vertex as visited.

Step 5: Choose another vertex, such that, the distance from source vertex is minimum.

Step 6: Now write down the cost for reaching it’s adjacent nodes form the starting node, such that the distance should be minimum.

Step 7: Repeat till all the nodes have been visited.

The process of choosing the length of the new path form source vertex to destination vertex is lesser than the current value, then update with the shortest value. This process is called as Relaxation.

The process of relaxation can be found below:

Consider the graph below:

Now, what is the cost from “a” to “b”? It is 5.

But there is a path from “a” to “b” with less cost.

i.e “a” -> “c” -> “b”. the cost is 3.

Hence we will use this path from “a” to “b” through “c”. Because the cost is less. This is called as Relaxation.

Now let’s understand this algorithm with the help of an example.

Consider the graph below:

We shall select node “a” as starting node, we shall make all the nodes from node “a” to all other nodes as infinity and distance form “a” to “a” is zero.

From node “a” check the adjacent nodes, i.e “b” and “c”, write down the cost in place of Infinity as the are less.

Now make node “a” as visited as all it’s adjacent nodes are visited.

Now, check for the nodes that are of less cost.

Node “b” cost form “a” is 2.

Node “c” cost from “a” is 3.

Hence we shall choose node “b”.

Now we shall relax all the nodes adjacent to node “b”. Only node “d” is adjacent to node “b”. Hence total cost from “a” to “d” is

- a -> b + b -> d
- 2 + 4 = 6

As 6 is less than INF, update the cost and make node “b” as visited.

Now we choose node “c” as the cost is less when compared to node “d”.

Now try to relax all the nodes that are adjacent to node “c”. Node “d” and node “e” are adjacent.

Hence total cost at node “d” is:

- a -> c + c-> d
- 3 + 1
- 4

Total cost at node “e” is:

- a->c + c->e
- 3+8
- 11

Now make node “c” as visited.

Now we choose node “d” as the cost is less than other 2 nodes.

Now relax all the edges adjacent to node d.

Node “c” and node “f” are adjacent.

Now total cost at node “c”:

- cost of node “d” + cost of “d” to “c”.
- 4 + 1
- 5

As “5” is greater tan “3”. Don’t update the value.

Total cost of node “f”:

- cost of node “d” + cost of “d” to “f”
- 4 + 9
- 13

13 is less than INF. Hence update and mark it as visited.

Now the cost is same for node “e” and node “f”. Choose any of the node.

We shall choose node “e”.

Node “e” and node “f” are adjacent.

Hence total cost of node “c”:

- cost of node “e” + cost of e -> c
- 11 + 8
- 19 > 3
- Hence don’t update.

Total cost of node “f”:

- Cost of node “e” + cost of e -> f
- 11 + 2
- 13
- Hence don’t update.

Make “e” as visited. Hence the solution

From the above steps we can use the below formula to calculate the code of the node.

Consider “u” as the source vertex.

“v” as the destination vertex.

Then if (distance(u) + cost of path (u, v) < distance_at (v)) then distance(v) = distance_at(u) + cost of path (u, v)

As you can see from the above image, Dijkstra’s algorithm us used to find the shortest path form source node to all other nodes, not just with the destination node.

## Implementation of Dijkstra Algorithm in C++

#include <iostream> #include <climits> using namespace std; const int numberVertex = 10; int minDistance(int distance[], bool ShortestPathTree[]) { int min = INT_MAX, min_index; for(int vertex = 0; vertex < numberVertex; vertex++) { if(ShortestPathTree[vertex] == false && distance[vertex] <= min) { min = distance[vertex]; min_index = vertex; } } return min_index; } void dijkstra(int graph[numberVertex][numberVertex], int source) { int distance[numberVertex]; bool ShortestPathTree[numberVertex]; for(int i = 0; i < numberVertex; i++) { distance[i] = INT_MAX; ShortestPathTree[i] = false; } distance[source] = 0; for(int count = 0; count < numberVertex - 1; count++) { int u = minDistance(distance, ShortestPathTree); ShortestPathTree[u] = true; for(int vertex = 0; vertex < numberVertex; vertex++) if(ShortestPathTree[vertex] == 0 && graph[u][vertex] != 0 && distance[u] != INT_MAX && distance[u] + graph[u][vertex] < distance[vertex]) distance[vertex] = distance[u] + graph[u][vertex]; } cout << "Distance from Source:" << endl; cout << "Vertex\t\tDistance" << endl; for(int i = 0; i < numberVertex; i++) cout << i << "\t\t" << distance[i] << endl; } int main() { int graph[numberVertex][numberVertex] = {{0, 14, 0, 7, 0, 0, 0, 8, 0, 10}, {14, 0, 8, 0, 0, 0, 0, 11, 0, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2, 0}, {7, 0, 7, 0, 9, 12, 0, 0, 0, 5}, {0, 0, 0, 9, 0, 0, 0, 0, 0, 0}, {0, 0, 4, 0, 0, 0, 2, 0, 0, 11}, {0, 0, 0, 12, 0, 2, 0, 1, 6, 15}, {8, 11, 0, 0, 0, 0, 1, 0, 7, 0}, {0, 0, 2, 0, 0, 0, 6, 7, 0, 0}, {10, 0, 0, 5, 0, 11, 15, 0, 0, 0}}; dijkstra(graph, 0); return 0; }

### Further Reading: