《【课件】第4章 最短路径问题》由会员分享，可在线阅读，更多相关《【课件】第4章 最短路径问题（46页珍藏版）》请在金锄头文库上搜索。
1、第4章最短路径问题 例1 8个城市v0 v1 v7之间有一个公路网 如图所示 每条公路为图中的边 边上的权数表示通过该公路所需的时间 设你处在城市v0 那么从v0到其他各城市 应选择什么路径使所需的时间最短 最短路径问题 最短路径问题 如果从图中某一顶点 称为源点 到达另一顶点 称为终点 的路径可能不止一条 如何找到一条路径 使得沿此路径各边上的权值总和达到最小 问题解法 权值为非负的单源最短路径问题 固定源点 Dijkstra算法 迪克斯特拉算法 1959 权值为任意值的单源最短路径问题 固定源点 Bellman Ford算法 贝尔曼 福特算法 所有顶点之间的最短路径问题 Floyd War
2、shall算法 弗洛伊德算法 1权值为非负的单源最短路径问题 问题的提出 给定一个带权有向图G与源点v 求从v到G中其它顶点的最短路径 限定各边上的权值大于或等于0 在图 a 中 考虑顶点0到其他顶点的最短距离是多少 顶点0到顶点1的最短路径距离是 20顶点0到顶点2的最短路径距离是 5顶点0到顶点3的最短路径距离是 22顶点0到顶点4的最短路径距离是 28顶点0到顶点5的最短路径距离是 12 思考 这些最短距离是怎么求出来的 为求得这些最短路径 Dijkstra提出按路径长度的递增次序 逐步产生最短路径的算法 首先求出长度最短的一条最短路径 再参照它求出长度次短的一条最短路径 依次类推 直到
3、从顶点v到其它各顶点的最短路径全部求出为止 在图 a 中 考虑顶点0到其他顶点的最短距离是多少 长度最短的最短路径是顶点0到顶点2的最短路径 就是顶点0到其他顶点的直接路径最短的路径 长度次短的最短路径是顶点0到顶点5的最短路径 v0 v2 v5 其中 v0 v2 就是前面求出的长度最短的最短路径 算法的基本思想 设置两个顶点的集合T和S S中存放已找到最短路径的顶点 初始状态时 集合S中只有一个顶点 即源点v0 T中存放当前还未找到最短路径的顶点 以后每求得一条最短路径 v0 vk 就将vk加入到顶点集合S中 直到所有的顶点都加入到集合S中 算法就结束了 可以证明v0到T中顶点vk的最短路径
4、 要么是从v0到vk的直接路径 要么是从v0经S中某个顶点vi再到vk的路径 证明 反证法 设v0到vk的最短路径上还有一个顶点vp T 算法的具体步骤 初始时 S中包含源点v0 然后不断从T中选取到顶点v0路径长度最短的顶点u 找到后 把顶点u加入到S 修改顶点v0到T中剩余顶点的最短路径长度值 T中各顶点新的最短路径长度值为 min 原来的最短路径长度值 顶点u的最短路径长度 u到该顶点的路径长度值 重复2 直到T的顶点全部加入S为止 在dijkstra算法里设置3个数组 dist n dist i 表示当前找到的从源点v0到终点vi的最短路径的长度 初始状态下 dist i 为E v0
5、i 即邻接矩阵的第v0行 S n S i 为0表示顶点vi还未加入到集合S中 S i 为1表示vi已经加入到集合S中 初始状态下 S v0 为1 其余为0 表示最初集合S中只有顶点v0 path n p i 表示在最短路径上顶点vi的前一个顶点号 在dijkstra算法里重复做以下工作 在dist 里查找S i 1 并且dist i 最小的顶点u 将S u 改为1 表示顶点u已经加入进来了 修改其它顶点的dist 及path 当S k 1 且顶点vu到顶点vk有边 E u k MAX 且dist u E u k dist k 则修改dist k 为dist u E u k 修改path k 为
6、u 递推公式 初始 dist k Edge v0 k v0是源点递推 dist k min dist k dist u Edge u k vk T其中vu是当前dist 最小的顶点 S dist 初始状态 S dist 1 S dist 2 3 4 5 path path path 源点为0 1 在T选取dist 最小的顶点u2 将u加入到S3 修改T中顶点的dist 及path 如何从dist 和path 中得到从源点到给定终点的最短路径及其长度 举例说明 设源点为0 终点为4 则path 4 1 path 1 2 path 2 0反过来排列 得到从源点0到终点4的最短路径为0 2 1 4
7、最短路径长度为dist 4 28 确定最短路径的方法 S dist 5 path 算法实现 defineMAX VER NUM10 顶点个数最大值 defineMAX1000000intEdge MAX VER NUM MAX VER NUM 邻接矩阵intvexnum 顶点个数voidDijkstra intv 假定图的邻接矩阵和顶点个数已经读进来了 从顶点v到顶点j的最短路径长度int dist newint vexnum 在最短路径上该顶点的前一顶点的顶点号int path newint vexnum int S newint vexnum S集合for inti 0 i vexnum
8、i dist i Edge v i S i 0 if i v 该算法可以实现的功能为 指定一个源点 指定一个终点 求源点到终点的最短路径 如最短路径存在 则输出最短路径 如果不存在 则输出 没有路径 S v 1 dist v 0 顶点v加入到顶点集合for i 0 i vexnum 1 i 从顶点v确定n 1条路径 intmin MAX u v 选择当前不在集合S中具有最短路径的顶点ufor intj 0 j vexnum j if S j endoffor 1 2 3 intt cout t intw t if path w 1 注意没有路径的情况 cout 从顶点 v 到顶点 t 没有路径
9、 endl return cout 从顶点 v 到顶点 t 的最短路径为 t while path w v cout path w w path w cout path w endl cout 路径长度为 dist t endl endofdijkstra 算法复杂度分析 用邻接矩阵存储图 Dijkstra算法的复杂度为O n2 Prim算法和Dijkstra算法的比较 思路都差不多 有空好好分析一下 Dijkstra算法 对S k 1的顶点 当dist u E u k dist k Prim算法 对nearvex j 1的顶点 取lowcost i min lowcost i AdjMatr
10、ix v j Dijkstra算法多了一个path数组 从而 ZOJ例题 ZOJ2008 2权值为任意值的单源最短路径问题 Dijkstra算法的局限性 图中边的权值不能为负值 S dist 初始状态 S dist 1 S dist 2 path path path Dijkstra算法 1 在T选取dist 最小的顶点u2 将u加入到S3 修改T中顶点的dist 及path 用Dijkstra算法求得顶点v0到顶点v2的最短距离是dist 2 即v0到v2的直接路径 长度为5 但从v0到v2的最短路径应该是 v0 v1 v2 其长度为2 思考 为什么Dijkstra算法应用到带负权值边的图中
11、 结果是错误的 S dist 初始状态 S dist 1 S dist 2 path path path S dist 初始状态 S dist 1 S dist 2 path path path Answer Dijkstra算法在利用顶点u的dist 去递推dist k 时 前提是dist u 是当前T集合中最小的 如果图中所有边的权值都是正的 这样推导是没有问题的 但是如果有负权值 这样推导是不正确的 例如第1次在T集合中找到dist 最小的是顶点2 dist 2 等于5 但是顶点2距离顶点0的最短路径 v0 v1 v2 长度是2 而不是5 S dist 初始状态 S dist 1 S d
12、ist 2 path path path Bellman Ford算法 为了能够求解边上带有负值的单源最短路径问题 Bellman 贝尔曼 和Ford 福特 提出了从源点逐次绕过其他顶点 以缩短到达终点的最短路径长度的方法 Bellman Ford算法的限制条件 要求图中不能包含权值总和为负值回路 负权值回路 如下图所示 Why Bellman Ford算法 Bellman Ford算法思想 Bellman Ford算法构造一个最短路径长度数组序列dist1 u dist2 u distn 1 u 其中 dist1 u 为从源点v到终点u的只经过一条边的最短路径长度 并有dist1 u Edg
13、e v u dist2 u 为从源点v最多经过两条边到达终点u的最短路径长度 dist3 u 为从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度 distn 1 u 为从源点v出发最多经过不构成负权值回路的n 1条边到达终点u的最短路径长度 算法的最终目的是计算出distn 1 u 为源点v到顶点u的最短路径长度 distk u 的计算 采用递推方式计算distk u 设已经求出distk 1 u u 0 1 n 1 此即从源点v最多经过不构成负权值回路的k 1条边到达终点u的最短路径的长度 从图的邻接矩阵可以找到各个顶点j到达顶点u的距离Edge j u 计算min di
14、stk 1 j Edge j u 可得从源点v绕过各个顶点 最多经过不构成负权值回路的k条边到达终点u的最短路径的长度 比较distk 1 u 和min distk 1 j Edge j u 取较小者作为distk u 的值 递推公式 求顶点u到源点v的最短路径 dist1 u Edge v u distk u min distk 1 u min distk 1 j Edge j u j 0 1 n 1 j u 例子 dist2 1 min dist1 1 min dist1 j Edge j 1 min 6 min dist1 0 Edge 0 1 dist1 2 Edge 2 1 算法实现
15、 defineMAX VER NUM10 顶点个数最大值 defineMAX1000000intEdge MAX VER NUM MAX VER NUM 图的邻接矩阵intvexnum 顶点个数voidBellmanFord intv 假定图的邻接矩阵和顶点个数已经读进来了 inti k u for i 0 i vexnum i dist i Edge v i 对dist 初始化if i v 注意 本算法使用同一个数组dist u 来存放一系列的distk u 其中k 0 1 n 1 算法结束时中存放的是distn 1 u path数组含义同Dijkstra算法中的path数组 for k 2
16、 kdist i Edge i u dist u dist i Edge i u path u i 如果dist 各元素的初值为MAX 则循环应该n 1次 即k的初值应该改成1 Dijkstra算法与Bellman算法的区别 Dijkstra算法和Bellman算法思想有很大的区别 Dijkstra算法在求解过程中 源点到集合S内各顶点的最短路径一旦求出 则之后不变了 修改的仅仅是源点到T集合中各顶点的最短路径长度 Bellman算法在求解过程中 每次循环都要修改所有顶点的dist 也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来 如果存在从源点可达的负权值回路 则最短路径不存在 因为可以重复走这个回路 使得路径无穷小 在Bellman算法中判断是否存在从源点可达的负权值回路的方法 思路 在求出distn 1 之后 再对每条边判断一下 加入这条边是否会使得顶点v的最短路径值再缩短 即判断 dist u w u v dist v 是否成立 如果成立 则说明存在从源点可达的负权值回路 代码如下 for i 0 idist i Edge i j return0 存在从
