那位高手能帮改一下
主要就是把下面代码改了，但实现功能要一样。《就是不能和下面代码相同》#include <stdio.h>
#include <LIMITS.H>
#define INFINITY INT_MAX
#define MAX_CITY_NUM 20
#define FALSE 0
#define TRUE 1
#define OK 0
#define ERR -1
typedef int Status ;
//城市结点
typedef struct tagCityNode
{
char name[256]; //城市名称
}CityNode;
typedef struct tagCityGraph
{
CityNode vexs[MAX_CITY_NUM]; //城市顶点向量
int arcs[MAX_CITY_NUM][MAX_CITY_NUM]; //邻接矩阵，代表距离
int vexnum, arcnum; //图的当前顶点数和弧数
}CityGraph;
Status InitGraph(CityGraph &cg)
{
printf("请输入城市数(小于等于20):");
scanf("%d",&cg.vexnum);
int i,j;
for( i = 0; i< cg.vexnum; i++)
{
printf("请输入城市%d的名称: ",i+1);
scanf("%s", cg.vexs[i].name);
}
printf("请交通网的边数(小于等于%d):", cg.vexnum * cg.vexnum);
scanf("%d",&cg.arcnum);
if(cg.arcnum > cg.vexnum * cg.vexnum)
cg.arcnum = cg.vexnum * cg.vexnum;
for(i =0; i<cg.vexnum; i++)
for (j =0; j<cg.vexnum; j++)
{
cg.arcs[i][j] = INFINITY;
}
printf("请输入城市邻接矩阵(格式为：城市序号 城市序号 距离):\n");
int distance;
int index1, index2;
for(i = 0; i<cg.arcnum; i++)
{
printf("%d. ",i+1);
scanf("%d %d %d", &index1, &index2, &distance);
index1 --, index2 --;
if( (index1 >= 0 && index1 < cg.vexnum) && (index2 >= 0 && index2 <cg.vexnum ))
{//两个都找到了
cg.arcs[index1][index2] = cg.arcs[index2][index1] = distance;
}
}
for (i = 0; i<cg.vexnum; i++)//同一城市距离为0
cg.arcs[i][i] = 0;
return OK;
}
void ShortestPath_FLOYD(CityGraph cg,int P[MAX_CITY_NUM][MAX_CITY_NUM][MAX_CITY_NUM], int D[MAX_CITY_NUM][MAX_CITY_NUM])
{
int u,v,w;
for(v=0; v<cg.vexnum; v++)
for(w=0; w<cg.vexnum ; w++)
{
D[v][w] = cg.arcs[v][w];
for(u = 0 ;u<cg.vexnum; u++)
P[v][w][u] = FALSE;
if( D[v][w] <INFINITY)
{//从v到w有直接路径
P[v][w][v] = TRUE;
P[v][w][w] = TRUE;
}
}
int i;
for(u=0; u<cg.vexnum; u++)
for(v=0; v<cg.vexnum; v++)
for(w=0; w<cg.vexnum; w++)
if((D[v][u] + D[u][w] >=0 ) && (D[v][u] + D[u][w] < D[v][w]))
{//从v经u到w的一条路径更短
D[v][w] = D[v][u] + D[u][w];
for( i = 0; i<cg.vexnum; i++)
P[v][w][i] = P[v][u][i] || P[u][w][i];
}
}
void Requests(CityGraph cg,int P[MAX_CITY_NUM][MAX_CITY_NUM][MAX_CITY_NUM], int D[MAX_CITY_NUM][MAX_CITY_NUM])
{
int index1, index2;
int i,j;
int city_in_path[MAX_CITY_NUM];
int path_cnt;
int icurrent, itmp;
printf("查询两城市之间的最短路径(格式：城市序号 城市序号):\n");
do{
scanf("%d %d", &index1, &index2);
index1 --, index2 --;
if( (index1 >= 0 && index1 < cg.vexnum) && (index2 >= 0 && index2 <cg.vexnum ))
{//两个都找到了
if(D[index1][index2] == INFINITY)
{
printf("两城市之间没有路径可以到达\n\n");
}
else
{--
path_cnt = 0;
printf("路径长度为:%d。\n",D[index1][index2]);
printf("路径：%s", cg.vexs[index1].name);
for(i = 0; i<cg.vexnum; i++)
if(P[index1][index2][i] == TRUE && i != index1 && i != index2)
{//i结点在最短的路径上, 除开始和结束结点外
city_in_path[path_cnt] = i;
path_cnt ++;
}
icurrent = index1;
for(i = 0; i<path_cnt; i++)
for(j = 0; j< path_cnt; j++)
{
itmp = city_in_path[j];
if(P[icurrent][itmp][itmp] == TRUE && city_in_path[j] != -1 )
{//找到与当前结点相连接的下一个结点
icurrent = itmp;
city_in_path[j] = -1;
printf("--%s", cg.vexs[itmp].name);
break;
}
}
printf("--%s\n\n", cg.vexs[index2].name);
}
}
else
{
printf("未找到相关城市\n\n");
}
}while(1);
}
int main()
{
CityGraph cg;
int DisMatrix[MAX_CITY_NUM][MAX_CITY_NUM];
int PathMatrix[MAX_CITY_NUM][MAX_CITY_NUM][MAX_CITY_NUM];
InitGraph(cg);
ShortestPath_FLOYD(cg, PathMatrix, DisMatrix);
Requests(cg, PathMatrix, DisMatrix);
return 0;
}
