Dijkstra’s Algorithm to find shortest path

Dijkstra’s Algorithm to find shortest path

Given a graph, directed or undirected and two nodes, find shortest path between these two nodes.
This is a standard problem and we don’t need to figure out what to do. We will have adjacency list representation of graph. 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 u.  Distance from source or start node to itself will be zero.
  3. Mark u as considered and distance finalized.
  4. Now for all neighbor nodes v of it, update the distance if the current distance 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 Bhas 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}
  5. Now select a node for which distance is not finalized and distance is minimum till now and make it u. Go to step 3.

Let’s work out an example and see how it works. Input graph is


Execution of above algorithm on this graph will be

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

Dijkstrat’s algorithm to find shortest path : Implementation

#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];

void add_edge_2(int i, int j, int wt);

int find_minimum_node(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 neihbour 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 cur_parent =0;
    while(cur_parent != -1){
        printf("%d ", end );
        cur_parent = parent[end];
        end = cur_parent;
    }
    printf("\n");
}

Node *createNode(int j, int wt){

	Node * new_node = (Node *)malloc(sizeof(Node));
	if(new_node){
		new_node->value = j;
		new_node->next = NULL;
		new_node->wt = wt;
	}
	else{
		printf("\n Node cannot be allocated");
	}
	return new_node;
}

void addEdge(int i, int j, int wt){

	Node * temp = graph[i];
	if(temp == NULL){
		graph[i] = createNode(j, wt);
	}
	else{
		while(temp->next){
			temp = temp->next;
		}
		temp->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;
}

The complexity of above code is O(V2) 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).
Limitation of algorithm1. It does not work with negative weights.

Please share if there is anything wrong or missing.