|
|
Program : 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 **********/
|
| Author: Shinu 31 May 2008 | Member Level: Gold Points : 2 |
Great To Know about it. I have been interested in this and happy to read more about it.Thanks for the information
|