最短路算法disktraPPT课件

1 最短路算法 2 最短路问题 最短路问题是网络理论中应用最广的问题之一 许多优化问题可以使这个模型 如设备更新 管道铺设 线路安排 厂区布局等 图论方法比较有效 最短路问题的一般提法如下 设G V E 为连通图 图中各边为图中任意两点 求一条道路 使他是从的所有道路中总权最小的道路 即 最小 3 内容 Dijkstra最优路线算法A 算法弗洛伊德算法最短路算法在交通中的应用 4 一 Dijkstra最优路线算法 Dijkstra算法的主要思想是用逐点增长的方法构造一棵路径树 从而得到从该树的根节点 即指定节点 到其它所有节点的最优路线 5 Dijkstra算法 6 标号法基本思想 7 标号的步骤 8 9 算例1 某地区四个城镇间的公路交通网 城镇1有一批货物需运往城镇4 网络边上的数据为综合运输费用 如何选择路线才能使总的综合运费最少 10 11 12 13 14 课堂练习1 利用Dijkstra算法 算出图中 v1到v5的最短路的长度 V1 V3 V2 V4 V5 4 3 2 7 5 8 10 1 15 传统Dijkstra算法的缺点 传统的Dijkstra算法将路网节点分为未标记节点 临时标记节点和永久标记节点三种类型 网络中所有节点初始化为未标记节点 在路线搜索过程中和最优路线节点相连通的节点为临时标记节点 每一次循环都是从临时标记节点中搜索距离起点路权总和最小的节点作为永久标记节点 直至找到目标节点或者所有节点都成为永久标记才结束算法 在传统的最优路线算法中 节点无序地存储在无序表中 每次搜索与当前检查点相邻的节点时 需要遍历所有的节点 这无疑成为算法搜索时的瓶颈 16 优化方法 解决的办法就是将所有与当前检查点相连的节点存储在一起 使每个搜索过程不必全部遍历或者只较少地遍历节点 这也是目前各种基于传统的Dijkstra算法的各种优化算法的重要出发点之一 另外一个优化途径就是尽量减少最优路线分析过程中搜索的临时标记节点的数量 从而尽快到达目标点 17 18 searchareaofDijkstra Ifh n thecostfromntothegoal thenA findsashortestpath Thegreaterh n is thelessnodesA expands themoreefficientA is Ifh n is0 Dijkstra salgorithm searchareaofA n s d f n g n h n A algorithmV S Dijkstraalgorithm Nodewithminimumf n selectedforexpansion g n h n 19 最短路算法在交通中的应用 路线优化算法是导航 诱导 商用车辆调度等系统的关键技术模块 决定系统的应用效率和结果的准确性 路线优化算法也是交通分配 选址的核心模块 20 算法流程 21 选址问题 已知某地区的交通网络如图5 39所示 其中点代表居民区 边表示公路 为小区间公路距离 问区中心医院建在哪个小区 可使距离医院最远的小区居民就诊时所走的路程最近 22 解 实际是要求出图的中心 可以化为一系列求最短路问题 先求出v1到其他各顶点的最短路长dj 令D v1 max d1 d2 d7 表示若医院建在v1 则离医院最远的小区距离为D v1 再依次计算v2 v3 v7到其余各点的最短路 类似求出D v2 D v3 D v