实验三 图及其应用 实验学时：2 实验类型：综合型 一、目的与任务 1．目的：掌握图的存储、构建、搜索等操作和应用，能用最短路径及其搜索等算法编制较综合性的程序，求解最优路线问题，进行程序设计、数据结构和算法设计等方面的综合训练。 2．任务：设计一个城市交通咨询模拟系统，利用该系统实现至少两种最优决策：最短路程到达、最省时到达等线路规划。 二、内容、要求与安排方式 1．实验内容： 用户驾车出行由于出行目的的不同对道路路线选择的要求也有不同。例如，有的希望在途中的路程尽可能短，有的则可能希望路程中时间最短。为了能满足广大旅客的需求，编制一个城市交通咨询模拟系统，选取城市部分位置、道路抽象为程序所需要图的顶点和边，并以城市道路长度（路程），道路的某时段的速度等信息作为图结点中的弧信息，为旅客提供这两种最优决策的交通咨询。 2．输入和输出： （1）输入形式： 构建图时，输入顶点、弧涉及的信息，包括：起始地、目的地、长度、该弧此时间段的平均速度等信息； 用户或者客户要输入出发地和目的地，并选择何种最优决策的路线规划。 （2）输出形式：根据用户需求输出对应信息 输出最短路程所需要的路线信息和最短路程； 输出最短时间所需要的路线信息和最短时间。 3．实验要求： 实现一个简单的交互式界面，包括系统菜单、清晰的输入提示等。 根据输入的交通图数据，以图形化形式把交通图显示在屏幕上。 以图形化形式把最优路线显示在屏幕上。 能够上机编辑、调试出完整的程序。 4．实验安排方式： 在实验课前编写出完整程序，在实验课时进行调试； 每组1人，独立完成上机实验。 三、注意事项： 请在实验报告中详细描述最优决策算法思想。
参考：交通路线图示例数据 假定根据城市道路抽象为如下图，起始地为V1顶点，目的地为V9顶点，对用弧上的距离和此时间段平均速度等信息如下表所示： 弧 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 距离 （Km） 12 8 6 5 8 7 5 6 10 6 8 速度 （Km / h） 40 50 60 20 25 55 20 20 40 30 25
【实现思路】 分别存储两种权值，分别对两种权值进行dijkstra 避免了使用高级数据结构，直接二维数组打一个算法模板即可。
【实现方法】 dijkstra
//solve.h #ifndef SOLVE_H_INCLUDED #define SOLVE_H_INCLUDED typedef struct{ int start, eend; int len, speed; }Node; #endif // SOLVE_H_INCLUDED //mian.cpp /** author:mmciel time:2019年5月16日22:35:55 问题描述： 多权值、单终点 Dijkstra 算法 */ #include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; const int maxn =105; int lmap[maxn][maxn];//路径作为权值的地图 double tmap[maxn][maxn];//时间作为权值的地图 int n,m;//节点数与路径数 int disl[maxn];//路径作为权值的最短路径表 int prevl[maxn];//路径作为权值的最短路径还原表 bool usel[maxn];//路径作为权值的是否访问标记 double dist[maxn];//时间作为权值的最短路径表 int prevt[maxn];//时间作为权值的最短路径还原表 bool uset[maxn];//时间作为权值的是否访问标记 int start,eend;//用户输入的起始地点与终止节点 vector<int> path;//路径还原的临时存储 vector<int> getPath(int t,int o);//路径的临时记录 void welcome();//欢迎界面 void InputData();//输入数据 void setData();//使用内部生成的数据 void dijkstral(int s);//对路径进行dijkstra算法 void dijkstrat(int s);//对时间（double值）进行dijkstra算法 void init();//清空地图、访问标记、路径还原、临时存储等变量的值 int main() { int order = -1; bool flag = true; while(1){ welcome(); cout<<"请输入命令："; cin>>order; switch(order){ case 1: init(); setData(); break; case 2: init(); InputData(); break; case 3: cout<<"请输入起点、终点："; cin>>start>>eend; dijkstral(start); cout<<"最短路径："; cout<<disl[eend]<<endl; path.clear(); path = getPath(eend,1); for(int i=0; i<path.size(); ++i) cout<<path[i]<<"->"; cout<<endl; break; case 4: cout<<"请输入起点、终点："; cin>>start>>eend; dijkstrat(start); cout<<"最短时间："; cout<<dist[eend]<<endl; path.clear(); path = getPath(eend,2); for(int i=0; i<path.size(); ++i) cout<<path[i]<<"->"; cout<<endl; break; break; default: cout<<"退出..."<<endl; flag = false; break; } if(!flag){ break; } } return 0; } void setData(){ n = 9; m = 11; lmap[1][2] = 12; lmap[1][3] = 8; lmap[1][4] = 6; lmap[2][5] = 5; lmap[3][5] = 8; lmap[4][6] = 7; lmap[5][7] = 5; lmap[5][8] = 6; lmap[7][9] = 10; lmap[8][9] = 6; tmap[1][2] = 12.0/40; tmap[1][3] = 8.0/50; tmap[1][4] = 6.0/60; tmap[2][5] = 5.0/20; tmap[3][5] = 8.0/25; tmap[4][6] = 7.0/55; tmap[5][7] = 5.0/20; tmap[5][8] = 6.0/20; tmap[7][9] = 10.0/40; tmap[8][9] = 6.0/30; cout<<"写入成功"<<endl; }