最短路径问题

图论及其应用1最短路径问题(ShortestPathProblem)图论及其应用2最短路径问题所谓最短路径问题（ShortestPathProblem）就是在一个带权图中找出两点之间的最短路径（权和最小的路径）。最短路径问题通常有如下几种类型：（1）带权（非负权）图中两个指定点之间的最短路径；（2）带权图（非负权）中任意两点间的最短路径；（3）带权图（非负权）中从一个指定点到其它所有点的最短路径；（4）带权图（非负权）中必须通过指定点的两个指定点之间的最短路径；（5）带权图（任意权）中最短路径问题，等等。图论及其应用3两个指定点之间的最短路径问题求解方法一：回溯法(从终点开始逐步逆向推算)主要步骤：先看与终点连接的结点，在结点上方写上该结点到终点的最短路线及权值；再将每个结点（与终点连接的结点）看成新的终点，以此类推，一直到起点为止。若在这过程中，一个结点同时与多个不同终点相连接，则该结点上方写上该结点到这些终点中最短的路线及权值；最终，起点上方的最短路线及权值即为起点到终点的最短路线及长度。图论及其应用4例使用回溯法求下图中结点1到结点10的最短路径3006-9-101508-101009-104005-8-102757-8-106002-6-9-105004-6-9-106003-5-8-106501-4-6-9-10图论及其应用5练习城市A到城市B的交通道路如下图所示，线上标注的数字为两点间距离(单位：万米)。某公司现需从A市紧急运送一批货物到B市。假设各条线路的交通状况相同，请为该公司寻求一条最佳路线。37-B68-B84-7-B95-7-B106-8-B161-5-7-B172-5-7-B131-6-8-B18A-1-5-7-B图论及其应用6指定点到其它所有点的最短路径解决这一问题最著名的方法是Dijkstra算法，这个算法是由荷兰计算机科学教授EdsgerW.Dijkstra在1959年提出的。他在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。图论及其应用7Dijkstra算法Dijkstra算法是由近及远地逐渐找出源点到其它任一点的最短路径。假设G=V,E,W是一个连通带权简单图，G中顶点为v0,v1,….,vn，假设v0为起点，边(vi,vj)（或vi,vj）的权记为wij，若(vi,vj)（或vi,vj）不是图中的边，则权为wij=，标号l(x)表示从v0到x的最短路径的长度。则Dijkstra算法原理如下：图论及其应用8Dijkstra算法的伪代码ProcedureDijkstra(G,W,a(,z))beginfori:=1tondol(vi):=l(a):=0S:=;//初始化标号及S，S用于保存已考察过的顶点的序列whileV(G)-S(zS)dobeginu:=不属于S且l(u)最小的一个顶点；ifu为顶点zS:=S{u}；elseS:=S{u}；for所有不属于S的顶点vdol(v):=min{l(v),l(u)+wuv}；endendDijkstra图论及其应用9例用Dijkstra算法求下图中从a到所有其它结点的最短路径及长度。图论及其应用10步骤uSabcdez0-01a{a}0422c{a,c}03210123b{a,c,b}0328124d{a,c,b,d}032810145e{a,c,b,d,e}032810136z{a,c,b,d,e,z}03281013l(v):=min{l(v),l(u)+wuv}图论及其应用11例用Dijkstra算法求下图中从A到其它所有结点的最短路径及长度图论及其应用12步骤uSABCDEFG0-01A{A}0712C{A,C}041543F{A,C,F}0411454114B{A,C,F,B}0411254115E{A,C,F,B,E}041125476G{A,C,F,B,E,G}04112547可以在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=min{Sj}，置P=P{k}，T=T-{k}。若T=，终止；否则，转向步骤3。步骤3：对T中每一点j，置Sj=min{Sj，Sk+wkj}，然后转向步骤2。算法经过n-1次循环结束。图论及其应用15任意两点间的最短路径Floyd算法Warshall算法图论及其应用16任意两点间的最短路径-Floyd算法首先定义两种矩阵运算：定义1已知矩阵A=(aij)ml，B=(bij)ln，规定C=AB=(cij)mn，其中cij=min(ai1+b1j,ai2+b2j,…,ail+blj)定义2已知矩阵A=(aij)mn，B=(bij)mn，规定C=AB=(dij)mn，其中dij=min(aij,bij)图论及其应用17例已知矩阵W，求WW121371236W图论及其应用18例已知矩阵W，求WWcij=min(ai1+b1j,ai2+b2j,…,ail+blj)121213713712123366WW23482364图论及其应用19121371236W23482364WWcij=min(ai1+b1j,ai2+b2j,…,ail+blj)图论及其应用20任意两点间的最短路径-Floyd算法算法原理：若W=(wij)nn是图G的权矩阵，计算W[2]，W[3]，…，W[n]及S，其中W[k]=W[k-1]W=(wij[k])nn；S=WW[2]W[3]…W[n]=(sij)nn。则wij[k]表示顶点i到顶点j经过k条边且权和最小的路径，sij表示顶点i到顶点j权和最小的路径（最短路径）。图论及其应用21例求下图中任意两点间最短路径的长度。121371236W图论及其应用22[2]121213713712123366W23482364[3][2]3465[4][3]6[2][3][4]S图论及其应用23由s16知，顶点v1到v6的最短路径为6；由s35知，顶点v3到v5的最短路径为2；由s45知，顶点v4到v5没有最短路径；[2][3][4]12346123512436S图论及其应用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，若in，转(4)；（6）k:=k+1，若kn，转(3)；否则停止。图论及其应用25例求下图中任意两点间最短路径的长度。121371236Wwij:=min(wij,wik+wkj)图论及其应用261213712136kW，****1248123712236kW，****12348123712336kW，***123461235124436kW，wij:=min(wij,wik+wkj)图论及其应用27***123461235124436kW，123461235124536kW，图论及其应用28Floyd算法的改进Floyd算法和Warshall算法只能给出任意两点间的最短路径的长度。改进的Warshall算法不仅能够给出任意两点间的最短路径的长度，同时也给出具体的最短路径。图论及其应用29改进后的Warshall算法算法原理：（1）输入图G的权矩阵W=(wij)nn和矩阵P=(pij)nn，其中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，若in，转(4)；（6）k:=k+1，若kn，转(3)；否则停止。矩阵P中pij的值是最短路径上从i到j被访问的最后一个顶点，所以利用该矩阵可以重构最短路径。图论及其应用30带负权图中的单源最短路径问题Dijkstra算法能够用于求带负权图中的指定两点间的最短路径？图论及其应用31例求下图中顶点a到c的最短路径。如果用Dijkstra算法，则求出的最短路径为ac，而不是abc。图论及其应用32带负权图中的单源最短路径问题Bellman-Ford算法该算法有一个限制条件，即要求图中不能包含权和为负值的回路。图论及其应用33Bellman-Ford算法Bellman-Ford算法的目的是构造一个最短路径长度数组序列dist1[v],dist2[v],…,distn-1[v]，其中dist1[v]表示从起点u到图中其它所有顶点v的只经过一条边的长度，distk[v]表示从起点u到顶点v的最多经过k条边的最短路径的长度。Bellman-Ford算法最终的目的是算出distn-1[v]。dist1[v]的生成：dist1[u]=0；若u,v是图中的有向边，则dist1[v]=wuv，否则dist1[