Dijkstra's Algorithm

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:

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) :

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