习题选讲-旅游规划.pdf
《习题选讲-旅游规划.pdf》由会员分享,可在线阅读,更多相关《习题选讲-旅游规划.pdf(5页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、图之 习题选讲图之 习题选讲 旅 游 规 划旅 游 规 划 题意理解题意理解 城市为结点城市为结点 公路为边公路为边 权重权重1:距离:距离 权重权重2:收费:收费 单源最短路单源最短路 Dijkstra 距离距离 等距离时按收费更新等距离时按收费更新 Sample Input: 4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20 0 3 12 1/20 2/30 4/10 2/20 1/20 核心算法核心算法 void Dijkstra( Vertex s ) while (1) V = 未收录顶点中未收录顶点中dist最小者最小者; i
2、f ( 这样的这样的V不存在不存在 ) break; collectedV = true; for ( V 的每个邻接点的每个邻接点 W ) if ( collectedW = false ) if ( distV+E distW ) distW = distV + E; pathW = V; costW = costV + C; else if ( (distV+E= distW) pathW = V; 其他类似问题其他类似问题 要求数最短路径有多少条要求数最短路径有多少条 counts = 1; 如果找到更短路:如果找到更短路:countW=countV; 如果找到等长路:如果找到等长路:countW+=countV; 要求边数最少的最短路要求边数最少的最短路 counts = 0; 如果找到更短路:如果找到更短路:countW=countV+1; 如果找到等长路:如果找到等长路:countW=countV+1;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
限制150内