# Dijkstra’s algorithm to find shortest path

Given a graph, directed or undirected and two nodes source and destination, find shortest path between these nodes using **Dijkstra’s algorithm**. Mathematically, problem can be stated as

Given a digraph G = (V, E), edge weights ℓe ≥ 0, source s ∈ V, and destination t ∈ V, find the shortest directed path from s to t.

Additional questions which follow are : can we use same algorithm to find shortest path from one source to all destination nodes in graph? Can we find shortest path from each node to each other node in graph using **Dijkstra’s shortest path algorithm**?

Coming back to original problem, let take an example, in below graph, shortest path between 1 and 4 is 1-3-2-4 with cost of 9.

Other paths are 1-2-4 with cost 11, 1-5-4 with cost 14 and so on.

Shortest path from a single source to a given destination is a classic graph problem. It finds application in **routing table generation in routers**, **optimum path from one point to another in maps, robot navigation, routing of telecommunication messages** and various other places.

In maps, there can be multiple routes from one source to given destination, but it highlights the shortest path. Similarly, consider a network where every path from each router has some weight associated with it. We wanted to forward packets on to a route so that total sum of those weights is least. All these problem are nothing but single source to destination shortest path problems.

There are many algorithms proposed to solve this problem. One of the algorithms is *Dijkstra’s algorithm*To apply Dijkstra’s algorithm to any graph two conditions are necessary :

- Graph should be connected.
- And weights on the edges should be non negative.

It does not matter if the graph is directed or undirected.

Important observation on which Dijkstra’s algorithm works is that every sub-path of an optimal path will also be optimal. Intuition is: take each vertex in the increasing order of their distance from source node and step by step create the tree adding one edge at a time. New edge is added in tree based on the criteria that is creates a shortest path to current vertex.

** Dijkstra’s algorithm **

Dijkstra’s algorithm is widely published and is as below.

1. Initialize distance of all nodes from start node as INFINITE and all nodes as not finalized. 2. Take source node to start with, let's say s. Distance from source or start node to itself will be zero. 3. Mark u as considered and distance finalized. Now for all neighbor nodes v of it, update the distance if the current distance of v from u is more than distance of u + weight of (u,v). For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.{From Wikipedia} 4. Now select a node for which distance is not finalized and distance is minimum till now and make it u. 5.Go to step 3.

### Mathematical explanation of Dijkstra’s shortest path algorithm

Distance of vertex *v* is estimated and stored in *d[v]* for each vertex *v*. If there is a path already discovered till v, then d[v] will be equal to less than then final distance between source and node *v*. If there is no path yet discovered, then *d[v]* will be infinity.

At beginning, *d[s]* will be 0 and *d[v]* will be infinity for all nodes.

How do we proceed forward and find shortest path to destination then? Each node (u) is process and new edge is added into tree. Processing means : for each node *v* adjacent to *u*, distance to v is updated (distance from s to u + distance from u to v) if that is less than *d[v]*

d[v] = d[u] + w(u,v) if d[u] is greater than d[u] + w(u,v)

If new d[v] is less than earlier d[v] stored then update d[v]. This step is also called as relaxation of edge. In programming terms relaxation function is :

void relax(){ if(d[v] > d[u] + w(u,v)){ d[v] = d[u] + w(u,v); pred[v] = u; } }

Vertex of graph are divided into two sets; set S is set of all the vertices whose real distance from source is known and there is another set VS whose real distance is still not known. Initially S ={} and all vertices belong to other set VS. As and when node is processed, it moves from VS to S.

What is the best method to find the next vertex to process? **Dijkstra algorithm uses greedy strategy** to select the next vertex to process. The next vertex will be u such that d[u] is minimum.

Let’s work out an example and see how shortest path algorithm works using greedy strategy.

Execution of above algorithm on this graph will be

To find path which was followed to reach destination from source, we can have an auxiliary array to keep track of parent node of current node whenever distance to current node is updated. By reverse tracking parents from destination to source, we can find out shortest path.

**Implementation of Dijkstra’s algorithm**

#include<stdio.h> #include<stdlib.h> #include<string.h> #define NUM_NODE 7 #define NUM_WORDS 10 #define NUM_CHAR 4 #define true 1 #define false 0 #define INFINITE 1000 typedef struct node{ int value; int wt; struct node *next; }Node; Node *graph[NUM_NODE + 1]; int findMinimumNode(int visited[], int dist[]){ int min = INFINITE; int index = -1; int i; for(i=1; i<= NUM_NODE; i++){ if(visited[i] == false && min > dist[i]){ min = dist[i]; index = i; } } return index; } void dijstras(Node * graph[], int start, int end ){ int i; int parent[NUM_NODE +1]; int distance[NUM_NODE+1]; int visited[NUM_NODE+1]; for(i=1; i<=NUM_NODE; i++){ visited[i] = false; distance[i] = INFINITE; parent[i] = -1; } // Mark distance of start as 0. distance[start] = 0; for(i=1; i<=NUM_NODE; i++){ int index = find_minimum_node(visited, distance); if(index != -1){ Node * node = graph[index]; Node * current = node->next; while(current){ /*If neighbor node is not visited and its current distance is more than distance of current node + cost of edge between current node and this node, update the distance */ if(visited[current->value] == false && distance[current->value] > distance[node->value] + current->wt){ distance[current->value] = distance[node->value] + current->wt; parent[current->value] = node->value; } current = current->next; } visited[node->value] = true; if(node->value == end) break; } else{ break; } } printf("\nDistance between %d and %d : %d", start , end, distance[end]); /* Printing path in reverse order,using stack, we can print it normal order to.*/ printf("\nPath is (In reverse order): "); int currentParent =0; while(currentParent != -1){ printf("%d ", end ); currentParent = parent[end]; end = currentParent; } printf("\n"); } Node *createNode(int j, int wt){ Node * newNode = (Node *)malloc(sizeof(Node)); if(newNode){ newNode->value = j; newNode->next = NULL; newNode->wt = wt; } else{ printf("\n Node cannot be allocated"); } return newNode; } void addEdge(int i, int j, int wt){ Node * currentNode = graph[i]; if(!currentNode){ graph[i] = createNode(j, wt); } else{ while(currentNode->next){ currentNode = currentNode->next; } currentNode->next = createNode(j, wt); } } //driver program int main(){ int i,j; for(i=1; i<=NUM_NODE; i++){ graph[i] = createNode(i,0); } // creating graph with weighted edges. addEdge(1,2,4); addEdge(1,3,8); addEdge(2,3,9); addEdge(2,4,9); addEdge(3,4,2); addEdge(2,5,10); addEdge(3,6,1); addEdge(4,5,7); addEdge(4,6,9); addEdge(5,6,6); addEdge(6,7,2); addEdge(7,5,5); dijstras(graph, 1, 6); return 0; }

Complexity of **Dijkstra’s algorithm** to find shortest path in a given directed graph is O(V^{2}) where V is number of vertices in graph. This can be reduced to O(E log V) by using heaps. Heaps will reduce complexity of searching minimum weight cost from O(V) to O(log V).

Implementation provided above can be optimized using priority queues. Use priority queue to store all nodes which are still not finalized. To start with put all nodes on to priority queue with key as d[v] and take out the minimum node, which will be source as d[s] =0 and rest all are infinity.

Implementation using priority queue can be done as

1. Create an empty priority queue. 2. For each node v ≠ s : d(v) ← ∞; d(s) ← 0. 3. For each node v ∈ V : insert v with key d(v) into priority queue. 4. while priority queue is not empty 4.1 u ← delete-min from priority queue. 4.2 For each edge (u, v) ∈ E leaving u: 4.2.1 If d(v) > d(u) + w(u, v) decrease-key of v to d(u) + w(u, v) in priority queue. d(v) ← d(u) + w(u, v).

It is very easy to implement this algorithm in any high level language like Python which provides ready to use implementation of priority queues.

**Limitation of algorithm**

1. It does not work with negative weights.

**Web resources **

Wikipedia

Animation

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us.