图最短路径-dijkstra算法.ppt

* * * * * * * 基本图算法 陈嘉庆 最短路径问题 单源最短路径 Single-Source Shortest Path 问题: 带权有向图G（E,V), 找出从给定源顶点s到其它顶点v的权最小路径。 “最短路径” = 最小权 路径的权是路径上所有边的权之和。 例：道路图 : 从华师中山附中到市政府的最短路径? 若顶点序列{V0,V1,…,Vn} 是从V0到Vn的最短路，则序列 {V0,V1,…,Vn-1} 必为从V0到Vn-1的最短路。 贪心算法 权非负的单源最短路径算法（Dijkstra） 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 2 v5 v4 v0 100 5 60 10 10 v1 v2 v3 20 50 30 图中从v0到其余各顶点之间的最短路径: v0到 v1 无 v0到 v2 (v0 ,v2 ) 10 v0到 v3 (v0 ,v4 , v3) 50 v0到 v4 (v0 ,v4) 30 v0到 v5 (v0 ,v4 , v3 ,v5) 60 单源最短路径 基本思想： 将图中所有顶点分成两组:S, V-S 一组是包括已确定最短路径的顶点的集合S，另一组是尚未确定的最短路径的顶点集V-S。 S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。 权非负的单源最短路径算法（Dijkstra） 权非负的单源最短路径算法（Dijkstra） 初始时,S仅包含源v0, 特殊路径： 从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。 步骤: (1) 取v0加入S中 (2) 从V-S中取出具有当前最短路径长度的顶点w加入S中。 最短路径——Dijkstra算法实例 * 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 2 例 求下图中顶点1到其余各顶点的最短路径。 1 0 12 3 ∞ ∞ ∞ 8 \ 5 \ 10 \ 3 6 4 14 \ 2 5 12 \ (1)初始化:1到v,若有边,则path[v]=边;dist[i]=边的值 (2)选出dist[i]为最小值,则path[i]为1到i的最短路径 (3)修改经过i更近的路径 (4)重复（2）（3） 最短路径——Dijkstra算法描述 方法如下： （其中：path[v]和dist[v]表示从v0到v的最短路径及其长度） （1）对v0以外的各顶点vi，若v0,vi存在， 则将其作为v0到vi的（暂时的）最短路径存放到path[v]中， 将其权值作为对应的路径长度存放到dist[v]中。 （2）从未解顶点中选择一个dist值最小的顶点v， 则当前的path[v]和dist[v]就是顶点v的最终解。 （3）由于某些顶点经过v可能会使得从v0到该顶点的路径更近 一些，因此，应修改这些顶点的路径及其长度的值。 （4）重复（2）（3），直到所有顶点求解完毕。 * 1 3 6 4 2 5 最短路径——Dijkstra算法实例 顶点 path dist 1 2 3 4 5 6 * 实例： 1 2 3 4 5 6 12 6 5 3 7 2 3 8 9 2 0 12 3 ∞ ∞ ∞ () (1,2) (1,3) () () () (1,3,2) 8 5 (1,3,4) (1,3,5) 10 (1,3,4,6) 14 (1,3,5,6) 12 Dijkstra算法： 一般情况下， Dist[k] = 源点到顶点 i 的弧上的权值 或者 = 源点到其它顶点的路径长度 + 其它顶点到顶点 i 的弧上的权值 设置辅助数组Dist，其中每个分量Dist[i] 表示 当前所求得的从源点到其余各顶点 i 的最短路径的长度。 1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。 2）修改其它各顶点的Dist[i]值。 假设求得最短路径的顶点为u， 若 Dist[u]+G.arcs[u][i]Dist[i] 则将 Dist[i] 改为 Dist[u]+G.arcs[u][i] V0和i之间存在弧 V0和i之间不存在弧 其中的最小值即为最短路径的长度。 单源最短路径 Single-Source Shortest Path Dijkstra的时间复杂度是O (N2)，它不能处理存在负边权的情况。 算法描述： 设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来