#include
#include
using namespace std ;
#define MUNum 20
#define INFINITY 32767
#define Myprintf cout << "\n\t+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-\n" << endl
typedef struct PlaneGraph
{
int PathLength ;
char Pathname[20] ;
}PlaneGraph,PG[MUNum][MUNum] ;
typedef struct
{
char name[20] ;
int num ;
}infor ;
typedef struct
{
infor vexs[MUNum] ;
PG arcs ;
int vexnum ,arcnum ;
}AMGraph ;
void InitGraph(AMGraph &G)
{
int i ,j ;
cout << "\t请输入校园地点的数量、校园小径的个数:" ;
cin >> G.vexnum >> G.arcnum ;//点 边
Myprintf ;
for(i=0 ;i<G.vexnum ;i++)
G.vexs[i].num = i ;//为点进行编号
cout << " 输入编号为(0-" << i << ")的校园地点的名称:\n\n" ;//店名称
for(i=0 ;i<G.vexnum ;i++)
{
cout << "\t" ;
cin >> G.vexs[i].name ;
}
cout << endl ;
Myprintf ;
for(i=0 ;i<G.vexnum ;i++)
for(j=0 ;j<G.vexnum ;j++)
{
G.arcs[i][j].PathLength = INFINITY ;
strcpy(G.arcs[i][j].Pathname,"null");
}
//输入路径信息
int v1,v2,w ;
char wn[20] ;
cout << "输入校园小径首尾地点编号、小径长度及小径名称\n\t(以-1 -1 -1 -1)结束输入:\n\t" << endl ;
cin >> v1 >> v2 >> w >> wn ;
while(v1!=-1 && v2!=-1 && w!=-1 && strcmp(wn,"-1")!=0)
{
cout << "\t" ;
G.arcs[v1][v2].PathLength = w ;
strcpy(G.arcs[v1][v2].Pathname,wn);
G.arcs[v2][v1].PathLength = w ;
strcpy(G.arcs[v2][v1].Pathname,wn);
cin >> v1 >> v2 >> w >> wn ;
}
Myprintf ;
}
//Floyd
void ShortestPath(AMGraph G)
{
int v,u,i,j,w,k,flag=1;
int p[MUNum][MUNum][MUNum],D[MUNum][MUNum];
for(v=0 ; v
for(w=0 ;w
{
D[v][w] = G.arcs[v][w].PathLength;
for(u=0;u
p[v][w][u] = 0 ;//
if(D[v][w]
p[v][w][v] = p[v][w][w] = 1;//
}
for(u=0 ;u
for(v=0 ;v
for(w=0 ;w
if(D[v][u]+D[u][w]
{
D[v][w] = D[v][u]+D[u][w];
for(i=0;i
p[v][w][i] = p[v][u][i] || p[u][w][i];//
}
while(flag)
{
cout
cin >> k >> j ;
if(k=G.vexnum || j=G.vexnum )
{
cout << "该地点不存在!请重新输入!" << endl ;
Myprintf ;
}
else if(k == j )
{
cout << "始点和终点相同!请重新输入!" << endl ;
Myprintf ;
}
else
flag = 0 ;
}
//输出信息
int L[MUNum];
L[0] = k;
int l = 1 ;
cout << "\t总路线长:" << D[k][j] << endl ;
cout << G.vexs[k].name ;
for(u=0 ;u<G.vexnum ;u++)
if(p[k][j][u] && k!=u && j!=u)
{
cout << " ——> " << G.vexs[u].name ;
L[l] = u ;
l++ ;
}
cout << " ——> " << G.vexs[j].name ;
L[l] = j ;
cout << endl ;
cout << "\t路线:" ;
for(u=0 ;u<l ;u++)
{
cout << G.arcs[L[u]] [L[u+1]].Pathname ;
if(u != l-1)
cout << " ——> " ;
}
cout << endl ;
Myprintf ;
}
int main()
{
cout << "\n----------------------------------校园导航----------------------------------" << endl << endl ;
AMGraph G ;
InitGraph(G) ;
char k[10] ;
strcpy(k,"Yes");
while(strcmp(k,"Yes")==0)
{
ShortestPath(G);
cout << "请问是否继续?Yes or No?" << endl ;
cin >> k ;
if(strcmp(k,"Yes") != 0 )
cout << "\n----------------------------------停止查询----------------------------------" << endl ;
}
return 0 ;
}
数据:
10 10
大学生活动中心
敬文图书馆
实验楼
行知楼
防空洞
宿舍楼
办公楼
外国语学院
美术学院
体育馆
0 1 10 逸夫路
1 3 15 敬文路
4 3 70 达夫路
1 2 20 朝阳路
3 7 77 富康路
4 5 12 人民路
5 6 19 孚玉路
6 7 56 龙门路
8 9 73 纬七路
8 7 8 九江路
-1 -1 -1 -1
在路线输入:1 9 和 9 1的时候路线不一样,请问怎么解决