Dijkstra algorithm is also called single source shortest path algorithm. It is based on “greedy” technique. The algorithm maintains a list ‘visited[ ]’ of vertices, whose shortest distance from the source is already known.
If visited, equals 1, then the shortest distance of vertex i is already known. Initially, visited[i] is marked as, for source vertex.
At each step, we mark visited[v] as 1. Vertex v is a vertex at shortest distance from the source vertex. At each step of the algorithm, shortest distance of each vertex is stored in an array ‘distance[ ]’.
1. Create cost matric C[ ][ ] from adjacency matrix adj[ ][ ]. C[i][j] is the cost of going from vertex i to vertex j. If there is no edge between vertices i and j then C[i][j] is infinity.
2. Array visited[ ] is initialized to zero.
3. If the vertex 0 is the source vertex then visited is marked as 1.
4. Create the distance matrix, by storing the cost of vertices from vertex no. 0 to n-1 from the source vertex 0.
Initial, distance of source vertex is taken as 0.
– Choose a vertex w, such that distance[w] is minimum and visited[w] is 0.
Mark visited[w] as 1.
– Recalculate the shortest distance of remaining vertices from the source.
– Only, the vertices not marked as 1 in array visited[ ] should be considered for recalculation of distance.
i.e. for each vertex v
The program contains two nested loops each of which has a complexity of O(n). n is number of vertices. So the complexity of algorithm is O(n2).
C Program on Dijkstra Algorithm for Finding Minimum Distance of Vertices from a Given Source in a Graph
#define INFINITY 9999
#define MAX 10
void dijkstra(int G[MAX][MAX],int n,int startnode);
printf(“Enter no. of vertices:”);
printf(“\nEnter the adjacency matrix:\n”);
printf(“\nEnter the starting node:”);
void dijkstra(int G[MAX][MAX],int n,int startnode)
//pred stores the predecessor of each node
//count gives the number of nodes seen so far
//create the cost matrix
//initialize pred,distance and visited
//nextnode gives the node at minimum distance
//check if a better path exists through nextnode
//print the path and distance of each node
printf(“\nDistance of node %d=%d”,i,distance[i]);