满意答案

//最近刚写了这个程序，希望对你有帮助

#include

#include

#include

#define MAXNODE 30 //定义最大节点数

#define MAXCOST 1000 //如果两点间无路劲，则设MAXCOST

int dist[MAXNODE],cost[MAXNODE][MAXNODE],n=6; //为实际节点数

//dijkstra算法求单源最短路径，这个函数就没加注释了，需要自己理解。

void dijkstra(int v0) //v0为起始节点

{

int s[MAXNODE];

int mindis,dis,i,j,u;

for(i=1;i<=n;i++)

{

dist[i]=cost[v0][i];

s[i]=0;

}

s[v0]=1;

for(i=1;i<=n;i++)

{

mindis=MAXCOST;

for(j=1;j<=n;j++)

{

if(s[j]==0 && dist[j]

{

u=j;

mindis=dist[j];

}

}

s[u]=1;

for(j=1;j<=n;j++)

if(s[j]==0)

{

dis=dist[u]+cost[u][j];

dist[j]=(dist[j]

}

}

}

//自定义display_path函数，输出各顶点最短路径

void display_path(int v0)

{

int i;

printf("\n顶点 %d 到各顶点的最短路径长度如下:\n",v0);

for(i=1;i<=n;i++)

{

printf(" (v%d->v%d):",v0,i);

if(dist[i]==MAXCOST)

printf("无路径");

else

printf("%d\n",dist[i]);

}

}

//主函数中各个定点的cost值可以根据实际路劲修改

void main()

{

int i,j,v0=1;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

cost[i][j]=((i==j)?0:MAXCOST);

cost[1][2]=10;

cost[1][4]=30;

cost[1][5]=100;

cost[1][6]=20;

cost[2][3]=50;

cost[3][5]=10;

cost[4][3]=20;

cost[4][5]=60;

cost[5][6]=30;

dijkstra(v0);

display_path(v0);

}

00分享举报