数据结构实验报告
交通指南系统
题目:
假设以一个带权有向图表示某一区域的公交线路网,图中顶点代表一些区域中的重要站点,弧长代表已有的公交线路,弧上的权表示该线路上的票价(或搭乘所需时间),试设计一个交通指南系统,指导前来咨询者以最低的票价或最少的时间从区域中的某一站点到达另一站点。
#include
using namespace std;
struct ArcCell
{
int adj; dj = 0;
else
[i][j].adj = 20000; nfo = false;
}
}
for(i = 0;i<;i++) dj = w; nfo)
{
delete [][i][j].info;
[i][j].info = false;
}
}
= 0;
= 0;
}
int MGraph::LocateVex(char u)
{
for(int i = 0 ;i<20;i++)
{
if(u == [i])
{
return i;
}
}
return -1;
}
void MGraph::ShortestPath_FLOYD(Path &P,Distanc &D)dj;// 顶点v到顶点w的直接距离
for(u = 0;u<;u++)
P[v][w][u] = false; //路径矩阵初值
if(D[v][w]<20000) //从v到w有直接路径
P[v][w][v] = P[v][w][w] = true;//由v到w的路径经过v和w两点}
}
for(u = 0;u<;u++)
{
for(v = 0;v<;v++)
{
for(w = 0;w<;w++)
{
if(D[v][u]+D[u][w] //从v经u到w的一条路径更短 { D[v][w] = D[v][u]+D[u][w];// 更新最短距离 for(i = 0;i<;i++) P[v][w][i] = P[v][u][i]||P[u][w][i];//从v到w的路径经过从v到u和从u到w的所有路径 } } } } } void main() { MGraph g; Path p; // 3维数组 Distanc d; // 2维数组 int s,t,k; char v1,v2; float sum=0; cout<<"\n***************欢迎使用交通查询系统**************\n"< (); cout<<"\n请输入出发站、目的站:"; cin>>v1>>v2; s= (v1); t= (v2); (p,d); if(s!=t) { int a=s; cout<<"\n由到途中经过:"; if(p[s][t][k] == 1) a=k; } } cout<<"最短线路总长:"< cout<<"\n\n***************祝您旅途愉快!*****************"< (); }