printf(\以下是最短路径：\\n\
case 3:
scanf(\
case 0:
}
}
printf(\以下是最短路径：\\n\
case 4:
printf(\以下是最短路径：\\n\
case 5:
printf(\以下是最短路径：\\n\
default : printf(\输入有误，请重新输入\\n\ printf(\
main();
}
printf(\
main();
case 3:
Floyd(g); printf(\请选择：\ printf(\
main();
scanf(\
exit(-1);break;
default: printf(\输入有误，请重新输入\\n\
printf(\
main();
}
6
3.2.2狄克斯特拉函数
初始化距离和路径，将s[]置为空。将远点编号v放入s中,循环直到所有顶点的最短路径都求出，将mindis置最小长度初值，选取不在s中且具有最小距离的顶点u将顶点u加入s中，修改不在s中的顶点的距离，输出最短路径 void Dijkstra(MGraph g,int v) { int dist[MAXV],path[MAXV]; int s[MAXV]; int mindis,i,j,u; for(i=0;i if(g.edges[v][i] path[i]=v; else path[i]=-1; } s[v]=1;path[v]=0; for(i=0;i mindis=INF; for(j=0;j u=j; mindis=dist[j]; } s[u]=1; for(j=0;j { 7 } } } dist[j]=dist[u]+g.edges[u][j]; path[j]=u; Dispath(dist,path,s,g.n,v); 3.2.3 Ppath函数 前向递归查找路径上的顶点，找到起点则返回，找顶点k的前一个顶点，输出顶点k。 void Ppath(int path[],int i,int v) { } 3.2.4 Dispath函数 有path函数计算最短路径，搜索最短路径的所有边，输出路径上的起点，输出路径上的中间点，输出路径上的终点。 void Dispath(int dist[],int path[],int s[],int n,int v) { int i; for(i=0;i if(s[i]==1&&dist[i]!=INF) { int k; k=path[i]; if(k==v) return; Ppath(path,k,v); printf(\ printf(\从%d到%d的最短路径长度为：%d\\t路径为：\ 8 } } printf(\ Ppath(path,i,v); printf(\} else printf(\从%d到%d不存在路径\\n\ 3.2.5弗洛伊德函数 设置路径长度A和路径path初值。做k次迭代，每次均试图将顶点K扩充到点钱球 得的从i到j的最短路径Pij上，修开路径长度，输出最短路径。 void Floyd(MGraph g) { int path[MAXV][MAXV],A[MAXV][MAXV]; int i,j,k; for(i=0;i for(j=0;j for(k=0;k if(A[i][j]>A[i][k]+A[k][j]) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } 3.2.6 Ppath2函数 向前递归查找路径上的顶点，找到了起点则返回，，找顶点i的前一个顶点k，找顶点k的前一个顶点j。在path中递归输出从顶点i到顶点j的最短路径 9 void Ppath2(int path[][MAXV],int i,int j) { int k; k=path[i][j]; if(k==-1)return; } 3.2.7 DisPath2函数 由path计算最短路径，若顶点i和顶点j之间没有边，则输出i到j没有路径，若有边则输出路劲上的起点、中间点和终点。 void Dispath2(int A[][MAXV],int path[][MAXV],int n) { int i,j; printf(\请输入起点和终点(i,j)：\ scanf(\ if(A[i][j]==INF) { if(i!=j) printf(\从%d到%d没有路径\\n\} else { printf(\从%d到%d路径为：\ Ppath2(path,i,k); printf(\Ppath2(path,k,j); printf(\ Ppath2(path,i,j); printf(\ printf(\路径长度为：%d\\n\} 10