4．交通咨询系统
任务：设计一个简易交通咨询系统，能让旅客咨询从人一个城市到另一个城市之间的最短路径。
功能要求：
（1）建立交通网络图的存储结构，并输出；
（2）求单源最短路径（Dijkstra算法），并输出；
（3）求任一对城市之间的最短路径，并输出。
第三个，无论我输入哪两个，都会显示无路径，这是为什么呢？求解
（ps:因为代码不是自己写的，所以想问问怎么解决）谢谢啦
#include<stdio.h>
#include<stdlib.h>
#define MVNum 100
#define Maxint 0
typedef char VertexType;
typedef int Adjmatrix;
int D1[MVNum],P1[MVNum];
int D[MVNum][MVNum],P[MVNum][MVNum];
typedef enum {FALSE,TRUE}boolean;
typedef struct{
VertexType vexs[MVNum] ;
Adjmatrix arcs[MVNum][MVNum];
}MGraph;
/*采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数*/
void CreateMGraph(MGraph *G,int n,int e)
{
int i,j,k,w;
for(i=1;i<=n;i++)
G->vexs[i]=(char)i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
G->arcs[i][j]=Maxint;
printf("输入%d条边的i,j及w: \n",e);
for(k=1;k<=e;k++)
{
scanf("%d,%d,%d",&i,&j,&w);
G->arcs[i][j]=G->arcs[j][i]=w;
}
printf("有向图的储存结构构建完毕！\n");
}
/*
用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路经p[v] 以及其权D[v]
设G是有向向图的邻接矩阵，若 边<i,j> 不存在，则G[i][j]=Maxint
S[v]为真当且仅当v属于S,即已求得从v1到v的最短路经
*/
void Dijkstra(MGraph G,int v1,int n)
{
int D2[MVNum],P2[MVNum];
int v,i,w,min;
boolean S[MVNum];
for(v=1;v<=n;v++)
{
S[v]=FALSE;
D2[v]=G.arcs[v1][v];
if(D2[v]<Maxint)
P2[v]=v1;
else
P2[v]=0;
}//end_for
D2[v1]=0;
S[v1]=TRUE;
//开始循环，每次求得v1到某个v顶点的最短路经，并将v加到S集总
for(i=2;i<n;i++)
{
min=Maxint;
for(w=1;w<=n;w++)
if(!S[w] && D2[w]<min)
{
v=w;
min=D2[w];
}
S[v]=TRUE;
for(w=1;w<=n;w++)
if(!S[w] && (D2[v]+G.arcs[v][w]<D2[w]))
{
//修改D2[w]和P2[w],w属于V-S
D2[w]=D2[v]+G.arcs[v][w];
P2[w]=v;
}//end_if
}//end_for
printf("路经长度 路经\n");
for(i=1;i<=n;i++)
{
printf("%5d",D2[i]);
printf("%5d",i);
v=P2[i];
while(v!=0)
{
printf("<-%d",v);
v=P2[v];
}
printf("\n");
}
}
/*弗洛伊德算法*/
void Floyd(MGraph G,int n)
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(G.arcs[i][j]!=Maxint)
P[i][j]=j;
else
P[i][j]=0;
D[i][j]=G.arcs[i][j];
}
//做k次迭代，每次迭代均试图将顶点k扩充到当前求得的从i到j的最短路经Pij上
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j])
{
D[i][j]=D[i][k]+D[k][j]; //修改长度
P[i][j]=P[i][k];
}
}
}
}
/*主函数*/
int main(void)
{
MGraph G;
int n,e,v,w,k;
int i,j;
int xz=1;
printf("输入图中顶点的个数和边数n,e:");
scanf("%d,%d",&n,&e);
CreateMGraph(&G,n,e);
printf("输出交通网络图的存储结构:\n");
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
printf("%d\t",G.arcs[i][j]);
printf("\n");
}
while(xz!=0)
{
printf("************求城市之间的最短路经************\n");
printf("============================================\n");
printf("1.求一个城市到所有城市的最短路经\n");
printf("2.求任意的两个城市之间的最短路经\n");
printf("============================================\n");
printf(" 请选择： 1 或 2 . 选择 0 退出 ：");
scanf("%d",&xz);
if(xz==2)
{
Floyd(G,n);
printf("请输入源点（或称起点）和终点： V , W : ");
scanf("%d,%d",&v,&w);
k=P[v][w];
if(k==0)
printf("顶点%d到%d无路经!\n",v,w);
else
{
printf("从顶点%d到%d的最短路经是：%d",v,w,v);
while(k!=w)
{
printf("->%d",k);
k=P[k][w];
}
printf("->%d\n",w);
printf(" 路经长度：%d\n",D[v][w]);
}
}
else
if(xz==1)
{
printf("求单源路经，输入源点 v : ");
scanf("%d",&v);
Dijkstra(G,v,n);
}
}
printf("结束求最短路经，再见！\n\n");
}
