Question

求迪杰斯特拉算法最短路径的算法，有输入与输出算法的C语言编程，谢谢！

Answer 1

输入和输出是用邻接矩阵描述的图么，如果是的话我把我的代码COPY给你：

#include <stdio.h>
#include <stdlib.h>

#define INFINITY 9999
#define MAX_VERTEX_NUM 20

typedef struct{
int vexs[MAX_VERTEX_NUM];
int arcs[20][20];
int vexnum,arcnum;
}MGraph;

void ShortestPath_DIJ(MGraph G,int v0,int D[]){
int *final,min,i,v,w,vex,path[20],j,path2[20];
printf("输入要到达的顶点：");
scanf("%d",&vex);
final=(int *)malloc(sizeof(int)*G.vexnum);
for(v=0;v<G.vexnum;++v){
final[v]=0;
D[v]=G.arcs[v0][v];
}
for(w=0;w<G.vexnum;w++){
if(G.arcs[v0][w]<INFINITY)
path[w]=v0;
else path[w]=-1;
}
D[v0]=0;final[v0]=1;path[v0]=-1;
j=1;
for(i=1;i<G.vexnum;++i){
min=INFINITY;
for(w=0;w<G.vexnum;++w)
if(!final[w]){
if(D[w]<min){
v=w;
min=D[w];
}
}
final[v]=1;
for(w=0;w<G.vexnum;++w)
if(!final[w]&&(min+G.arcs[v][w]<D[w])){
D[w]=min+G.arcs[v][w];
path[w]=v;
}
}
printf("两顶点之间的最短距离为%d\n\n",D[vex]);
printf("两顶点间的最短路径为：");
for(w=0;w<G.vexnum;w++)
path2[w]=-1;
i=1;path2[0]=vex;w=vex;
while(path[w]!=-1){
path2[i++]=path[w];
w=path[w];
}

for(w=G.vexnum-1;w>=0;w--){
if(path[vex]==-1){
printf("%d到%d间不存在可行路径",v0,vex);
break;
}
if(path2[w]!=-1)
printf("%d ",path2[w]);
}
printf("\n");
printf("\n");
}

int main(){
int D[20],i,j,v0;
MGraph G;

for(i=0;i<20;i++)
G.vexs[i]=i;
for(i=0;i<20;i++)
for(j=0;j<20;j++)
G.arcs[i][j]=INFINITY;
G.vexnum=6;G.arcnum=8;
G.arcs[0][2]=10;G.arcs[0][4]=30;
G.arcs[0][5]=100;G.arcs[1][2]=5;
G.arcs[2][3]=50;G.arcs[3][5]=10;
G.arcs[4][3]=20;G.arcs[4][5]=60;

for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++)
printf("%4d ",G.arcs[i][j]);
printf("\n");
}
while(1){
printf("输入出发的顶点：");
scanf("%d",&v0);
ShortestPath_DIJ(G,v0,D);
}
system("pause");
}