Dijkstra's Algorithm

Getting from one node in a graph to another while expending the least cost is important in many domains. This article discusses Dijkstra's algorithm and its implementation.

The basic idea behind the algorithm is that the shortest path between two points X and Y includes the shortest path between X and an intermediate point W.

Logically, the idea can be proved as : Consider a shortest path between X and Y that goes through W. Now, the path can be broken down into X to W and W to Y. If the selected path from X to W is not the shortest, then there exists another path from X to W which is the shortest, and hence our path from X to Y can be further shortened, making our first statement (given path from X to Y is shortest) is wrong. Hence, for a path to be the shortest, its intermediate paths should also be the shortest.

Here is an example of Dijkstra's Algorithm taken from the book, Introduction to Algorithms:

dijkstra algorithm for shortest path graph in c

Some points to be noted about Dijkstra's Algorithm:

  • It supports only non-negative weights
  • It can be used for both directed graphs and undirected graphs
  • It uses greedy strategy to compute the shortest path, although the answer obtained is proved to be correct

Here is the algorithm in its raw form:

DIJKSTRA ( G , w , s )
1 INITIALIZE-SINGLE-SOURCE ( G , s )
2 S = empty 
3 Q = G.V 
4 while ( Q = !empty ) 
5     u = EXTRACT-MIN ( Q )
6     S = S U { u }
7     for each vertex v E G.Adj(u)
8         RELAX ( u , v , w )

Once we have the algorithm, it's easy to implement it in code. Below is the implementation in C language.

#include <stdio.h>
#include <stdlib.h>
int G[20][20] , distance[20] , inSet[20] , q[20] , parent[20] ;
void print( int V )
{
    int i ;
    for ( i = 0 ; i < V ; i++ )
        printf("i = %d parent = %d distance from source = %d \n", i + 1 , parent[i] , distance[i] ) ;
}
int Q( int V )
{
    int sum = 0 , i ;
    for( i = 0 ; i < V ; i++ )
        sum += q[i] ;
    return sum ;
}
int extractMin( int V )
{
    int i , idx , min = 1000 ;
    for ( i = 0 ; i < V ; i++ )
    {
        if ( distance[i] <= min && inSet[i] == 0 )
            min = distance[i] , idx = i ;
    }
    q[idx] = 0 ;
    return idx ;
}
void dijkstra ( int S , int V )
{
    int u , i , check_empty = Q(V);

    while( check_empty >0 )
    {
        u = extractMin(V) ;

        inSet[u] = 1 ;
        q[u] = 0 ;
        for( i = 0 ; i < V ; i++ )
        {
            if( G[u][i] > 0 )
            {
                if( distance[u] + G[u][i] < distance[i] )
                    distance[i] = distance[u] + G[u][i] , parent[i] = u + 1 ;
            }
        }
        check_empty = Q(V);
    }

    print(V);
}
int main()
{
    int V , i , j , S;
    printf ( "Enter no. of vertices: " ) ;
    scanf ( "%d" , &V ) ;

    printf ( "Enter graph in matrix form:\n" ) ;
    for ( i = 0 ; i < V ; i++ )
    {
        for( j = 0 ; j < V ; j++ )
            scanf( "%d" , &G[i][j] );
    }
    for ( i = 0 ; i < V ; i++ )
        distance[i] = 1000 , inSet[i] = 0 , q[i] = 1 , parent[i] = -1 ;

    printf ( "Enter the source vertex: " ) ;
    scanf ( "%d" , &S ) ;
    distance[ S - 1 ] = 0 ;
    dijkstra ( S , V ) ;
    return 0;
}

We run the code in the example graph above. Here is the output (note that -1 means no parent) :

dijkstra algorithm for shortest path graph in c


Source: The Daily Programmer, http://www.thedailyprogrammer.com/2015/07/dijkstra-algorithm.html
Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 License.

Last modified: Monday, November 16, 2020, 8:19 PM