Dijkstra’s Algo – single source shortest path Implementation, Pseudocode & Explanation
In our previous post Application of Graph – Shortest Path Problems we discussed the findings of the optimal path or the shortest path between the nodes of a graph. We talk about Single Source Shortest Path Problem in the above post.
In this tutorial, we will cover,
- Implementation of Dijkstra’s Algo with two approaches
- Its drawback and solution Bellman-Ford Algo
Implementation of Dijkstra’s Algorithm:
Given the graph and the source, find the shortest path from source to all the nodes. That’s the problem statement. Following is the algo,
Dijkstra(G, W, S)
Initialize single source (G, S)
S = Φ
Q = G.V //Q, priority Queue data structure
Until Q not Empty
u = extract-min(Q)
S = S U {u}
for each vertex v ∈ G.adj(u)
relax(u, v, W)
Our implementation will be using the Adjacency List Representation of the graph taking O(E*LogV), Matrix representation could also be used but, that takes O(V2). In the adjacency list graph representation, each vertex u of an adjacency list for vertex v will be containing the weight of u-v.
Following is the structure declaration of vertex u.
typedef struct linkedListNode{
int vertex;
int weight;
struct linkedListNode *next;
}listNode;
Read – How to represent a Graph
MinHeap will be used for priority queue that’ll take the least time. MinHeap will be constructed based on distance to each vertex.
Relaxing is like updating the distances if found a shorter path through the current vertex. However, for updating a node, we should be knowing the position of that node in the heap but, no such operation could be possible with the standard heap. Hence, as a result, the position of vertex needs to be maintained as well. Also, a node in the heap will be containing distance along with the vertex i.e.
typedef struct HeapNode{
int distance;
int vertexID;
}heapNode;
Following is the structure declaration of the required heap data structure. heapsize represents the size of the heap at the moment. capacity as the name justifies. positionOfVertex, to apply the decreaseKey operation(updating the distance) directly to the node. array as the array of above defined nodes.
typedef struct HeapDataStructure{
int heapSize;
int capacity;
int *positionOfVertex;
heapNode *array;
}Heap;
Interestingly, there could be two approaches followed and both would be taking the same running time. Heap data structure and Graph representation will be followed same in both the approach. We’ll be using two arrays also, dist[i] where the shortest distance from source to i is maintained here and visited[i] that says, vertices, those are extracted are in the visited set and need not be taken into consideration during relaxation. The important point to note is every time heap is restructured the position of vertex must be updated accordingly.
Approach1:
This one is the commonly seen, it says build the minHeap with all the vertices where distance is taken infinity into consideration. The source vertex distance will be zero. First, source is extracted and the distance of adjacent ones is updated. Next time the vertex with shortest distance is extracted and adjacent ones updated and so on.
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
/* use the gcc 5.4 or above, for lower version, all the declaration should be at the
* top of respective block*/
/*It's a heap that contain vertex as well as the distance to source element specified*/
typedef struct HeapNode{
int distance;
int vertexID;
}heapNode;
/* PositionOfVertex[]:
* since we need to update the distance if require, therefore position of vertex must be
* known in advance otherwise we end up searching the whole heap, to decrease the distance
* of a vertex. In every operation of heap, whenever heap is restructured postion of vertex
* will be updated as well*/
typedef struct HeapDataStructure{
int heapSize;
int capacity;
int *positionOfVertex;
heapNode *array;
}Heap;
Heap *minHeap;
heapNode* createNewHeapNode(int vertexID, int distance); //creating the node as required
Heap *createHeap(int capacity);
void insert(Heap *minHeap, heapNode *);
void decreaseKey(int nDistance, int index);
heapNode extractMin();
void minHeapify(int );
void swap(int , int );
heapNode* createNewHeapNode(int vertexID, int distance){
heapNode* temp = (heapNode*)malloc(sizeof(heapNode));
temp->vertexID = vertexID;
temp->distance = distance;
return temp;
}
Heap *createHeap(int capacity){
Heap *minHeap;
minHeap = (Heap *)malloc(sizeof(Heap));
minHeap->array = (struct HeapNode *)\
malloc( sizeof(struct HeapNode)*capacity );
minHeap->capacity = capacity;
minHeap->heapSize = 0;
minHeap->positionOfVertex = (int *)malloc(capacity * sizeof(int));
return minHeap;
}
void insert(Heap *minHeap, heapNode *nNode){
int temp = minHeap->heapSize;
if(minHeap->heapSize == minHeap->capacity){
printf("Heap overflow\n");
return ;
}
minHeap->heapSize++ ;
minHeap->array[temp] = *nNode;
minHeap->positionOfVertex[nNode->vertexID] = temp;
if(minHeap->heapSize == 1){
return ;
}
while(minHeap->array[(temp-1)/2].distance > nNode->distance && temp != 0){
minHeap->array[temp] = minHeap->array[(temp-1)/2];
int k = minHeap->array[temp].vertexID;
minHeap->positionOfVertex[k] = temp;
temp = (temp-1)/2;
}
minHeap->array[temp] = *(nNode);
minHeap->positionOfVertex[nNode->vertexID] = temp;
}
void decreaseKeyMinHeap(int nDistance, int index){
if(minHeap->array[index].distance <= nDistance)
printf("Invalid operation\n");
else{
heapNode tmp = minHeap->array[index];
tmp.distance = nDistance;
int temp = index;
while(minHeap->array[(temp-1)/2].distance > nDistance && temp != 0){
minHeap->array[temp] = minHeap->array[(temp-1)/2];
int k = minHeap->array[temp].vertexID;
minHeap->positionOfVertex[k] = temp;
temp = (temp-1)/2;
}
minHeap->array[temp] = tmp;
minHeap->positionOfVertex[tmp.vertexID] = temp;
}
}
heapNode extractMin(){
heapNode extractedMinNode;
/*in the calling function if the return contains the vertex "-1", means underflow*/
extractedMinNode.vertexID = -1;
if(minHeap->heapSize == 0){
printf("Heap Underflow\n");
return extractedMinNode;
}
else{
int temp = minHeap->heapSize-1;
extractedMinNode = minHeap->array[0];
minHeap->array[0] = minHeap->array[temp];
int k = minHeap->array[temp].vertexID;
minHeap->positionOfVertex[k] = 0;
minHeap->heapSize--;
minHeapify(0);
printf("Key Extracted:%d\n", extractedMinNode.vertexID);
return extractedMinNode;
}
}
void minHeapify(int i){
int L, R, smallest;
L = 2*i+1; R = 2*i+2;
if(L <= minHeap->heapSize-1 && \
minHeap->array[L].distance < minHeap->array[i].distance)
smallest = L;
else
smallest = i;
if(R <= minHeap->heapSize-1 && \
minHeap->array[R].distance < minHeap->array[smallest].distance)
smallest = R;
if(smallest != i){
swap(i, smallest);
minHeapify(smallest);
}
}
void swap(int i, int j){
int k = minHeap->array[i].vertexID, l = minHeap->array[j].vertexID;
int m = minHeap->positionOfVertex[k];
/*swaping two node of the heap involves swaping of postion as well */
minHeap->positionOfVertex[k] = minHeap->positionOfVertex[l];
minHeap->positionOfVertex[l] = m;
heapNode tmp = minHeap->array[i];
minHeap->array[i] = minHeap->array[j];
minHeap->array[j] = tmp;;
}
int isMinHeapEmpty(){
if(!minHeap->heapSize)
return 1; //heap non-empty
else
return 0;
}
typedef struct linkedListNode{
int vertex;
int weight;
struct linkedListNode *next;
}listNode;
typedef struct adjecencyList{
listNode *head;
}adjList;
typedef struct graph{
int nVertices; //number of vertices in the graph
int nEdges; //number of vertices in the graph
adjList *array; // array of adjacency list
}Graph;
Graph *addEdge(Graph *, int , int, int );
Graph *createAdjListOfGraph(Graph *, int, int);
void printGraph(Graph *);
Graph *createAdjListOfGraph(Graph *g, int noVertices, int noEdges){
g = (Graph *)malloc(sizeof(Graph));
g->nVertices = noVertices; g->nEdges = noEdges;
/*size of array of adjacency list will be total number of vertices */
g->array = (adjList *)malloc(sizeof(adjList) * g->nVertices);
for(int i = 0; i < g->nVertices; i++)
g->array[i].head = NULL;
return g;
}
Graph *addEdge(Graph *g, int u, int v, int weight){
listNode *temp1, *temp2;
/* each node in a adjacency list contain the distance between it and the head node of the list*/
temp1 = (listNode *)malloc(sizeof(listNode));
temp1->vertex = v;
temp1->weight = weight;
temp1->next = g->array[u].head;
g->array[u].head = temp1;
temp2 = (listNode *)malloc(sizeof(listNode));
temp2->vertex = u;
temp2->weight = weight;
temp2->next = g->array[v].head;
g->array[v].head = temp2;
return g;
}
void dijkstras(Graph *g, int srcVertex){
/* dist[j] will contain the distances from source to j*/
int dist[g->nVertices]; int visited[g->nVertices];
int minHeapCapacity = g->nVertices;
minHeap = createHeap(minHeapCapacity);
/* visited shows everytime a vertex is exctraced, it becomes visited. Means next time,
* visited node will not be checked from its adjacent node if there's shorted path as
* shortest path is already calculated*/
/*initializing the heap with each nodes distances as infinity and visited as all 0 */
insert(minHeap, createNewHeapNode(srcVertex, 0)); visited[0] = 0; dist[srcVertex] = 0;
for(int i = 1; i < g->nVertices; i++){
insert(minHeap, createNewHeapNode(i, INT_MAX));
visited[i] = 0;
}
while(!isMinHeapEmpty()){
heapNode extractedNode = extractMin();
int v = extractedNode.vertexID; visited[v] = 1; int vDist = extractedNode.distance;
/*checking out all the adjacent vertex and updating the distances if shorter found */
listNode *temp = g->array[v].head;
while (temp){
int u = temp->vertex; int nDistance = vDist + temp->weight;
/* temp->weight is the cost/distance of edge v to u*/
if(!visited[u]){
int posU = minHeap->positionOfVertex[u]; int uDist = minHeap->array[posU].distance;
if(nDistance < uDist){
dist[u] = nDistance;
decreaseKeyMinHeap(dist[u], posU);
}
}
temp = temp->next;
}
}
int i = -1;
printf("\nVertexID\tShortest Distance to source");
while(++i < g->nVertices)
printf("\n%d\t\t%d", i, dist[i]);
}
int main(void){
Graph *g = NULL;
g = createAdjListOfGraph(g, 6, 9);
g = addEdge(g, 0, 1, 7);
g = addEdge(g, 0, 5, 14);
g = addEdge(g, 0, 2, 9);
g = addEdge(g, 1, 2, 10);
g = addEdge(g, 1, 3, 15);
g = addEdge(g, 2, 3, 11);
g = addEdge(g, 2, 5, 2);
g = addEdge(g, 3, 4, 6);
g = addEdge(g, 4, 5, 9);
dijkstras(g, 0);
return 0;
}
Output:-
Key Extracted:0
Key Extracted:1
Key Extracted:2
Key Extracted:5
Key Extracted:3
Key Extracted:4
VertexID Shortest Distance to source
0 0
1 7
2 9
3 20
4 20
5 11
Approach2:
This one says, instead of building minHeap with all the vertices, build with the source vertex only and every time a vertex is extracted its adjacent ones are inserted. In case some or all the adjacent ones are already in the heap, then just update the distance if found shorter distance.
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct HeapNode{
int distance;
int vertexID;
}heapNode;
typedef struct HeapDataStructure{
int heapSize;
int capacity;
int *positionOfVertex;
heapNode *array;
}Heap;
Heap *minHeap;
heapNode* createNewHeapNode(int vertexID, int distance);
Heap *createHeap(int capacity);
void insert(Heap *minHeap, heapNode *);
void decreaseKey(int nDistance, int index);
heapNode extractMin();
void minHeapify(int );
void swap(int , int );
heapNode* createNewHeapNode(int vertexID, int distance){
heapNode* temp = (heapNode*)malloc(sizeof(heapNode));
temp->vertexID = vertexID;
temp->distance = distance;
return temp;
}
Heap *createHeap(int capacity){
Heap *minHeap;
minHeap = (Heap *)malloc(sizeof(Heap));
minHeap->array = (struct HeapNode *)\
malloc( sizeof(struct HeapNode)*capacity );
minHeap->capacity = capacity;
minHeap->heapSize = 0;
minHeap->positionOfVertex = (int *)malloc(capacity * sizeof(int));
return minHeap;
}
void insert(Heap *minHeap, heapNode *nNode){
int temp = minHeap->heapSize;
if(minHeap->heapSize == minHeap->capacity){
printf("Heap overflow\n");
return ;
}
minHeap->heapSize++ ;
minHeap->array[temp] = *nNode;
minHeap->positionOfVertex[nNode->vertexID] = temp;
if(minHeap->heapSize == 1){
return ;
}
while(minHeap->array[(temp-1)/2].distance > nNode->distance && temp != 0){
minHeap->array[temp] = minHeap->array[(temp-1)/2];
int k = minHeap->array[temp].vertexID;
minHeap->positionOfVertex[k] = temp;
temp = (temp-1)/2;
}
minHeap->array[temp] = *(nNode);
minHeap->positionOfVertex[nNode->vertexID] = temp;
}
void decreaseKeyMinHeap(int nDistance, int index){
if(minHeap->array[index].distance <= nDistance)
printf("Invalid operation\n");
else{
heapNode tmp = minHeap->array[index];
tmp.distance = nDistance;
int temp = index;
while(minHeap->array[(temp-1)/2].distance > nDistance && temp != 0){
minHeap->array[temp] = minHeap->array[(temp-1)/2];
int k = minHeap->array[temp].vertexID;
minHeap->positionOfVertex[k] = temp;
temp = (temp-1)/2;
}
minHeap->array[temp] = tmp;
minHeap->positionOfVertex[tmp.vertexID] = temp;
}
}
heapNode extractMin(){
heapNode extractedMinNode;
extractedMinNode.vertexID = -1;
if(minHeap->heapSize == 0){
printf("Heap Underflow\n");
return extractedMinNode;
}
else{
int temp = minHeap->heapSize-1;
extractedMinNode = minHeap->array[0];
minHeap->array[0] = minHeap->array[temp];
int k = minHeap->array[temp].vertexID;
minHeap->positionOfVertex[k] = 0;
minHeap->heapSize--;
minHeapify(0);
printf("Key Extracted:%d\n", extractedMinNode.vertexID);
return extractedMinNode;
}
}
void minHeapify(int i){
int L, R, smallest;
L = 2*i+1; R = 2*i+2;
if(L <= minHeap->heapSize-1 && \
minHeap->array[L].distance < minHeap->array[i].distance)
smallest = L;
else
smallest = i;
if(R <= minHeap->heapSize-1 && \
minHeap->array[R].distance < minHeap->array[smallest].distance)
smallest = R;
if(smallest != i){
swap(i, smallest);
minHeapify(smallest);
}
}
void swap(int i, int j){
int k = minHeap->array[i].vertexID, l = minHeap->array[j].vertexID;
int m = minHeap->positionOfVertex[k];
minHeap->positionOfVertex[k] = minHeap->positionOfVertex[l];
minHeap->positionOfVertex[l] = m;
heapNode tmp = minHeap->array[i];
minHeap->array[i] = minHeap->array[j];
minHeap->array[j] = tmp;;
}
int isMinHeapEmpty(){
if(!minHeap->heapSize)
return 1; //if heap is non-empty
else
return 0;
}
typedef struct linkedListNode{
int vertex;
int weight;
struct linkedListNode *next;
}listNode;
typedef struct adjecencyList{
listNode *head;
}adjList;
typedef struct graph{
int nVertices; //number of vertices in the graph
int nEdges; //number of vertices in the graph
adjList *array; // array of adjacency list
}Graph;
Graph *addEdge(Graph *, int , int, int );
Graph *createAdjListOfGraph(Graph *, int, int);
void printGraph(Graph *);
Graph *createAdjListOfGraph(Graph *g, int noVertices, int noEdges){
g = (Graph *)malloc(sizeof(Graph));
g->nVertices = noVertices; g->nEdges = noEdges;
/*size of array of adjacency list will be total number of vertices */
g->array = (adjList *)malloc(sizeof(adjList) * g->nVertices);
for(int i = 0; i < g->nVertices; i++)
g->array[i].head = NULL;
return g;
}
Graph *addEdge(Graph *g, int u, int v, int weight){
listNode *temp1, *temp2;
temp1 = (listNode *)malloc(sizeof(listNode));
temp1->vertex = v;
temp1->weight = weight;
temp1->next = g->array[u].head;
g->array[u].head = temp1;
temp2 = (listNode *)malloc(sizeof(listNode));
temp2->vertex = u;
temp2->weight = weight;
temp2->next = g->array[v].head;
g->array[v].head = temp2;
return g;
}
void dijkstras(Graph *g, int srcVertex){
int dist[g->nVertices]; int visited[g->nVertices];
int minHeapCapacity = g->nVertices;
minHeap = createHeap(minHeapCapacity);
for(int i = 0; i<g->nVertices; i++){
dist[i] = INT_MAX; visited[i] = 0;}
insert(minHeap, createNewHeapNode(srcVertex, 0)); dist[0] = 0; dist[srcVertex] = 0;
while(!isMinHeapEmpty()){
/* insertion of node in the heap, done only after each exctraction*/
heapNode exctractedNode = extractMin(); int v = exctractedNode.vertexID; visited[v] = 1;
int vDist = exctractedNode.distance;
listNode *temp = g->array[v].head;
while(temp){
int u = temp->vertex; int v_u_weight = temp->weight;
int nDistance = vDist + v_u_weight;
if(dist[u] == INT_MAX){
dist[u] = nDistance;
insert(minHeap, createNewHeapNode(u, nDistance));
}
else{
/*adjacent nodes are present in the heap, if visited[u] = 0 */
if(!visited[u]){
int uPos = minHeap->positionOfVertex[u];
if(nDistance < dist[u]){
dist[u] = nDistance;
decreaseKeyMinHeap(dist[u], uPos);
}
}
}
temp = temp->next;
}
}
int i = -1;
printf("\nVertexID\tShortest Distance to source");
while(++i < g->nVertices)
printf("\n%d\t\t%d", i, dist[i]);
}
int main(void){
Graph *g = NULL;
g = createAdjListOfGraph(g, 6, 9);
g = addEdge(g, 0, 1, 7);
g = addEdge(g, 0, 5, 14);
g = addEdge(g, 0, 2, 9);
g = addEdge(g, 1, 2, 10);
g = addEdge(g, 1, 3, 15);
g = addEdge(g, 2, 3, 11);
g = addEdge(g, 2, 5, 2);
g = addEdge(g, 3, 4, 6);
g = addEdge(g, 4, 5, 9);
dijkstras(g, 0);
return 0;
}
Output:-
Key Extracted:0
Key Extracted:1
Key Extracted:2
Key Extracted:5
Key Extracted:3
Key Extracted:4
VertexID Shortest Distance to source
0 0
1 7
2 9
3 20
4 20
5 11
Analyzing time complexity:
The main factor is checking the distances if shorter is there. In worst case every edge could be checked i.e. every edge is relaxed. This would take O(E). This relaxation is basically decreaseKey taking O(LogV), the total time would be O(E*LogV). We can also consider the building time of minHeap, but, that takes O(V) i.e. the bigger one is O(E*LogV).
Drawback:
What if the graph contains a negative weight cycle. In such case, Dijkstra’s algo fail, as it keeps on updating the distances. See below,
In the next step C will be updated as 1. In further steps, B and C vertices keep on updating themselves. That’s the worst part. This is happening because of the negative weight cycle between vertex B and C. Therefore, any graph with a negative weight cycle between any number of vertices lead to Dijkstra’s algo stuck in updating unnecessarily.
Solution: Bellman-Ford Algo
It says utmost any edge will be relaxed (distance updated between two vertices) utmost V-1 times. If in V time relaxation, the better path is achieved, then, the graph contains negative weight cycle and thus stop the algo mentioning shortest path can’t be achieved. However, if no better path is achieved, then, simply apply the Dijkstra’s algo. Therefore, this algo is similar to Dijkstra’s algo beside the checking part. This relaxation of each edges V times, results in the running time O(E*V), which is bigger than O(E*LogV). Hence, Bellman-Ford Algo is applied only at required place i.e. when we are not sure that the graph will always contain only non negative cycles/.
An investment in knowledge always pays the best interest. Hope you like the tutorial. Do come back for more because learning paves way for a better understanding.
Do not forget to share and Subscribe.
Happy coding!! 🙂
nice one. but, for reading longer line of comment/code, box is smaller need to move right everytime. either decrease code font size or increase the size of box
Thank you for your words and feedback.
We will take care of it in future 🙂