We have already studied two major graph traversal techniques : Breadth First Search and Depth First Search. In this post, we will be studying Dijkstra's Algorithm for finding the shortest path from a source vertex to all other vertices.
Our program is based on the algorithm provided in the book, Introduction to Algorithms, CLRS. 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) :
 |
| Output for Dijkstra's Algorithm |
