Program to compute shortest path using dijkstras technique.

/**********************************************************************/

/*Program : To show Dijkstra’s Algorithm*/

/*Purpose : Program to compute shortest path in graph*/

/*Date : 07-01-2005*/

/*Time : 17:10*/

/**********************************************************************/

#include

#include

#include

#define INF INT_MAX

#define v 10

#define F 0

#define T 1

typedef int adj_mat[v][v];

typedef struct graph_tag

{

int nodes;

int path[v];

int dist[v];

int visited[v];

adj_mat cost;

}graph;

/**************Function Declaration Begin**********/

void dijkstra(graph *);

/**************Function Declaration End**********/

void main()

{

graph G;

clrscr();

printf(“\n\t\t Dijkstras Algorithm:”);

printf(“\n\t\t This program finds the shortest path of a directed graph\n”);

printf(“\n\t\t Enter number of vertices required in the graph:\n”);

scanf(“%d”,&G.nodes);

dijkstra(&G);

getch();

}

/********** dijkstras technique for shortest path **********/

/********** Function Definition begins **********/

void dijkstra(graph *G)

{

int i,j,k=0,x,y,p,min;

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

printf(“\n\t\t Enter cost for visiting vertex %d to vertex %d:\n”,i,j);

scanf(“%d”,&G->cost[i][j]);

}

}

printf(“\n\t\t Cost Adjacency matrix of a graph is: \n”);

for(i=0;inodes;i++)

{

for(j=0;jnodes;j++)

{

printf(“%3d\t”,G->cost[i][j]);

}

printf(“\n”);

}

printf(“The shortest path of the graph is :\n”);

G->visited[0]=T;

G->dist[0]=0;

G->path[0] = 0;

printf(“%d\n”,G->path[0]);

k++;

for(y=1;ynodes;y++)

{

G->visited[y] = F;

G->dist[y] = G->cost[0][y];

}

for(i=1;inodes;i++)

{

min = INF;

for(x=1;xnodes;x++)

{

if(!G->visited[x])

if(G->dist[x]

{

y = x;

min = G->dist[x];

}

}

G->visited[y] = T;

for(x=1;xnodes;x++)

if(!G->visited[x])

if(min + G->cost[y][x]dist[x])

G->dist[x] = min + G->cost[y][x];

G->path[k] = y;

for(p=0;p<=k;++p)

printf(“%d\t”,G->path[p]);

k++;

printf(“\n”);

}

}

/********** Function Definition ends **********/