Program to implement Dijkstra's algorithm
ALGORITHM :
Dijkstra( G , s )
//Input:
A weighted connected graph G=< V , E > and its vertex v in V
//Output:
The length dv of a shortest path from s to v and its
//penultimate
vertex pv for every vertex v in V.
Step
1:Initialize ( Q ) //initialize vertex priority in the priority queue.
Step 2:
for every vertex v in V do {
Step 3:
dv = infinity
Step 4:
pv = NULL
Step 5:
Insert(Q, v , dv )//initialize vertex priority in the priority queue
} //end for
Step 6:
ds = 0
Step 7:
Decrease ( Q , s , ds ) //update
priority of s with ds
Step 8:
Vt = 0
Step 9:
for I = 0 to | V | - 1 do {
Step
10:u* = DeleteMin ( Q ) //delete the
minimun priority element
Step
11:vt = vt U { u* }
Step
12:for every vertex u in V – Vt that is adjacent to u* do {
Step
13:if (du* + w ( u*, u ) < du ) {
Step
14:du = du* + w ( u*, u )
Step
15:pu = u*
Step
16:Decrease ( Q , u , du )
} // end if
} // end for
} // end for
Example:
Now lets come to an example which further illustrates above algorithm. Consider a weighted graph.
Source Code
#include "stdio.h"#include "conio.h"#define infinity 999void dij(int n,int v,int cost[10][10],int dist[]){ int i,u,count,w,flag[10],min; for(i=1;i<=n;i++) flag[i]=0,dist[i]=cost[v][i]; count=2; while(count<=n) { min=99; for(w=1;w<=n;w++) if(dist[w]<min && !flag[w]) min=dist[w],u=w; flag[u]=1; count++; for(w=1;w<=n;w++) if((dist[u]+cost[u][w]<dist[w]) && !flag[w]) dist[w]=dist[u]+cost[u][w]; }}void main(){ int n,v,i,j,cost[10][10],dist[10]; clrscr(); printf("\n Enter the number of nodes:"); scanf("%d",&n); printf("\n Enter the cost matrix:\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&cost[i][j]); if(cost[i][j]==0) cost[i][j]=infinity; } printf("\n Enter the source matrix:"); scanf("%d",&v); dij(n,v,cost,dist); printf("\n Shortest path:\n"); for(i=1;i<=n;i++) if(i!=v) printf("%d->%d,cost=%d\n",v,i,dist[i]); getch();}
