Now ... C
/* dijkstra_shortestPath2c.c */ /* 2014-12-02 */
/* A C program for Dijkstra's single source shortest path algorithm.
The program is for adjacency matrix representation of the graph */
/*
Edited version here taken from original at:
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
*/
#include <stdio.h>
#include <limits.h>
#define INF INT_MAX
#define V 9 /* Number of vertices in the graph */
/* A utility function to find the vertex with minimum distance value, from
the set of vertices not yet included in shortest path tree */
int minDistance( const int dist[], const int sptSet[] )
{
int min = INF, /* Initialize min value */
min_index = -1, /* added -1 */
vi;
for( vi = 0; vi < V; ++vi )
{
if ( !sptSet[vi] && dist[vi] < min ) /* changed from <= */
min = dist[vi], /* update values ... */
min_index = vi;
}
return min_index;
}
/* A utility function to print the constructed distance array */
void printSolution( int src, const int dist[], const char* cities[] )
{
int i;
printf( "Destination Distance from %s\n", cities[src] );
for( i = 0; i < V; ++i )
if( i != src )
printf( "%11s %21d\n", cities[i], dist[i] ) ;
}
/* Function that implements Dijkstra's single source shortest path algorithm
for a graph represented using adjacency matrix representation */
void dijkstra( int src, const int graph[V][V], const char* cities[] )
{
int i,
count;
int dist[V]; /* The output array, dist[i], will hold the shortest
distance from src to i */
int sptSet[V]; /* sptSet[i] == 1 if vertex i is included in shortest
path tree or shortest distance from src to i is finalized */
/* Initialize all distances as INFINITE and sptSet[] as 0 */
for( i = 0; i < V; ++i )
dist[i] = INF , sptSet[i] = 0;
/* Distance of source vertex from itself is always 0 */
dist[src] = 0;
/* Find shortest path for all vertices */
for( count = 0; count < V-1; ++count )
{
/* Pick the minimum distance vertex from the set of vertices not
yet processed. u is always equal to src in first iteration. */
int vi,
u = minDistance( dist, sptSet );
if( u == -1 ) break; /* I also added this line ... */
/* Mark the picked vertex as processed */
sptSet[u] = 1;
/* Update dist value of the adjacent vertices of the picked vertex. */
for( vi = 0; vi < V; ++vi )
{
/* Update dist[vi] only if is not in sptSet, there is an edge from
u to v, and total weight of path from src to v through u is
smaller than current value of dist[vi] */
if( !sptSet[vi] && graph[u][vi] /* && dist[u] != INF <- re. possible overflow,
but? handled by prev. condition: '&& graph[u][vi]' */
&& dist[u]+graph[u][vi] < dist[vi] )
dist[vi] = dist[u] + graph[u][vi];
}
}
/* print the constructed distance array */
printSolution( src, dist, cities );
}
int main() /* driver program to test above function */
{
int start = 0;
const char* cities[] =
{
"City 0", "City 1", "City 2", "City 3", "City 4",
"City 5", "City 6", "City 7", "City 8"
} ;
const int graph[V][V] = /* Create an example graph ... */
{
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0,11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9,14, 0, 0, 0 },
{ 0, 0, 0, 9, 0,10, 0, 0, 0 },
{ 0, 0, 4, 0,10, 0, 2, 0, 0 } ,
{ 0, 0, 0,14, 0, 2, 0, 1, 6 },
{ 8,11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
} ;
for( ; start < V; ++start )
{
printf( "\nPress 'Enter' to start at %s ... ", cities[start] );
while( getchar() != '\n' );
dijkstra( start, graph, cities );
}
printf( "\nPress 'Enter' to exit ... " ); fflush( stdout );
while( getchar() != '\n' );
return 0;
}
/*
Output:
Press 'Enter' to start at City 0 ...
Destination Distance from City 0
City 1 4
City 2 12
City 3 19
City 4 21
City 5 11
City 6 9
City 7 8
City 8 14
Press 'Enter' to start at City 1 ...
Destination Distance from City 1
City 0 4
City 2 8
City 3 15
City 4 22
City 5 12
City 6 12
City 7 11
City 8 10
Press 'Enter' to start at City 2 ...
Notes:
1) The code calculates shortest distance,
but doesn’t calculate the path information.
We can create a parent array, update the parent array when
distance is updated (like prim’s implementation) and use it
to show the shortest path from source to different vertices.
2) The code is for undirected graph, same dijekstra function
can be used for directed graphs also.
3) The code finds shortest distances from source to all vertices.
If we are interested only in shortest distance from source to
a single target, we can break the for loop when the picked
minimum distance vertex is equal to target (Step 3.a of algorithm).
4) Time Complexity of the implementation is O(V^2). If the input
graph is represented using adjacency list, it can be reduced
to O(E log V) with the help of binary heap. We will soon be discussing
O(E Log V) algorithm as a separate post.
5) Dijkstra’s algorithm doesn’t work for graphs with negative
weight edges. For graphs with negative weight edges,
Bellman–Ford algorithm can be used, we will soon be discussing
it as a separate post.
*/
