《最短路径问题》PPT课件

1,最短路径问题(ShortestPathProblem),2,最短路径问题,所谓最短路径问题（ShortestPathProblem）就是在一个带权图中找出两点之间的最短路径（权和最小的路径）。最短路径问题通常有如下几种类型：（1）带权（非负权）图中两个指定点之间的最短路径；（2）带权图（非负权）中任意两点间的最短路径；（3）带权图（非负权）中从一个指定点到其它所有点的最短路径；（4）带权图（非负权）中必须通过指定点的两个指定点之间的最短路径；（5）带权图（任意权）中最短路径问题，等等。,3,两个指定点之间的最短路径问题,求解方法一：回溯法(从终点开始逐步逆向推算)主要步骤：先看与终点连接的结点，在结点上方写上该结点到终点的最短路线及权值；再将每个结点（与终点连接的结点）看成新的终点，以此类推，一直到起点为止。若在这过程中，一个结点同时与多个不同终点相连接，则该结点上方写上该结点到这些终点中最短的路线及权值；最终，起点上方的最短路线及权值即为起点到终点的最短路线及长度。,4,例使用回溯法求下图中结点1到结点10的最短路径,5,练习城市A到城市B的交通道路如下图所示，线上标注的数字为两点间距离(单位：万米)。某公司现需从A市紧急运送一批货物到B市。假设各条线路的交通状况相同，请为该公司寻求一条最佳路线。,6,指定点到其它所有点的最短路径,解决这一问题最著名的方法是Dijkstra算法，这个算法是由荷兰计算机科学教授EdsgerW.Dijkstra在1959年提出的。他在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。,7,Dijkstra算法,Dijkstra算法是由近及远地逐渐找出源点到其它任一点的最短路径。假设G=是一个连通带权简单图，G中顶点为v0,v1,.,vn，假设v0为起点，边(vi,vj)（或）的权记为wij，若(vi,vj)（或）不是图中的边，则权为wij=，标号l(x)表示从v0到x的最短路径的长度。则Dijkstra算法原理如下：,8,Dijkstra算法的伪代码,ProcedureDijkstra(G,W,a(,z)beginfori:=1tondol(vi):=l(a):=0S:=;/初始化标号及S，S用于保存已考察过的顶点的序列whileV(G)-S(zS)dobeginu:=不属于S且l(u)最小的一个顶点；ifu为顶点zS:=Su；elseS:=Su；for所有不属于S的顶点vdol(v):=minl(v),l(u)+wuv；endendDijkstra,9,例用Dijkstra算法求下图中从a到所有其它结点的最短路径及长度。,10,步骤uSabcdez0-01aa0422ca,c03210123ba,c,b0328124da,c,b,d032810145ea,c,b,d,e032810136za,c,b,d,e,z03281013,l(v):=minl(v),l(u)+wuv,11,例用Dijkstra算法求下图中从A到其它所有结点的最短路径及长度,12,步骤uSABCDEFG0-01AA0712CA,C041543FA,C,F0411454114BA,C,F,B0411254115EA,C,F,B,E041125476GA,C,F,B,E,G04112547,可以在Dijkstra算法的基础之上以如下方法找到最短路径：从终点往回走，找到它的前导顶点，使得它们之间的标号的差等于连接它们边的权重，如此下去直至到起点，从而找到一条最短路径。,13,作业用Dijkstra算法求出下图中从顶点a到其它所有顶点的最短路径及及长度。,14,有向图中求最短路径的Dijkstra算法,设Sj是带权有向图G中自顶点1到顶点j的最短有向路的长度步骤1：置P=1，T=2,3,n且S1=0，Sj=w1j，j=2,3,n。步骤2：在T中寻找一点k，使得Sk=minSj，置P=Pk，T=T-k。若T=，终止；否则，转向步骤3。步骤3：对T中每一点j，置Sj=minSj，Sk+wkj，然后转向步骤2。算法经过n-1次循环结束。,15,任意两点间的最短路径,Floyd算法Warshall算法,16,任意两点间的最短路径-Floyd算法,首先定义两种矩阵运算：定义1已知矩阵A=(aij)ml，B=(bij)ln，规定C=AB=(cij)mn，其中cij=min(ai1+b1j,ai2+b2j,ail+blj)定义2已知矩阵A=(aij)mn，B=(bij)mn，规定C=AB=(dij)mn，其中dij=min(aij,bij),17,例已知矩阵W，求WW,18,例已知矩阵W，求WW,cij=min(ai1+b1j,ai2+b2j,ail+blj),19,cij=min(ai1+b1j,ai2+b2j,ail+blj),20,任意两点间的最短路径-Floyd算法,算法原理：若W=(wij)nn是图G的权矩阵，计算W2，W3，Wn及S，其中Wk=Wk-1W=(wijk)nn；S=WW2W3Wn=(sij)nn。则wijk表示顶点i到顶点j经过k条边且权和最小的路径，sij表示顶点i到顶点j权和最小的路径（最短路径）。,21,例求下图中任意两点间最短路径的长度。,22,23,由s16知，顶点v1到v6的最短路径为6；由s35知，顶点v3到v5的最短路径为2；由s45知，顶点v4到v5没有最短路径；,24,任意两点间的最短路径-Warshall算法,算法原理：（1）输入图G的权矩阵W；（2）置k:=1；（3）置i:=1；（4）修改矩阵W中的权值，wij:=min(wij,wik+wkj)，j=1,2,n；（5）i:=i+1，若in，转(4)；（6）k:=k+1，若kn，转(3)；否则停止。,25,例求下图中任意两点间最短路径的长度。,wij:=min(wij,wik+wkj),26,wij:=min(wij,wik+wkj),27,28,Floyd算法的改进,Floyd算法和Warshall算法只能给出任意两点间的最短路径的长度。改进的Warshall算法不仅能够给出任意两点间的最短路径的长度，同时也给出具体的最短路径。,29,改进后的Warshall算法,算法原理：（1）输入图G的权矩阵W=(wij)nn和矩阵P=(pij)nn，其中pij=i。（2）置k:=1；（3）置i:=1；（4）修改矩阵W和P中的值，wij:=min(wij,wik+wkj)，j=1,2,n；pij=pkj，j=1,2,n；（5）i:=i+1，若in，转(4)；（6）k:=k+1，若kn，转(3)；否则停止。,矩阵P中pij的值是最短路径上从i到j被访问的最后一个顶点，所以利用该矩阵可以重构最短路径。,30,带负权图中的单源最短路径问题,Dijkstra算法能够用于求带负权图中的指定两点间的最短路径？,31,例求下图中顶点a到c的最短路径。,如果用Dijkstra算法，则求出的最短路径为ac，而不是abc。,32,带负权图中的单源最短路径问题,Bellman-Ford算法该算法有一个限制条件，即要求图中不能包含权和为负值的回路。,33,Bellman-Ford算法,Bellman-Ford算法的目的是构造一个最短路径长度数组序列dist1v,dist2v,distn-1v，其中dist1v表示从起点u到图中其它所有顶点v的只经过一条边的长度，distkv表示从起点u到顶点v的最多经过k条边的最短路径的长度。Bellman-Ford算法最终的目的是算出distn-1v。dist1v的生成：dist1u=0；若是图中的有向边，则dist1v=wuv，否则dist1v=。distkv的生成：distkv=mindistk-1v,mindistk-1j+wjv。,34,例：