最短路径问题课件

最短路径问题

(ShortestPathProblem)1最短路径问题

(ShortestPathProblem)最短路径问题所谓最短路径问题（ShortestPathProblem）就是在一个带权图中找出两点之间的最短路径（权和最小的路径）。最短路径问题通常有如下几种类型：（1）带权（非负权）图中两个指定点之间的最短路径；（2）带权图（非负权）中任意两点间的最短路径；（3）带权图（非负权）中从一个指定点到其它所有点的最短路径；（4）带权图（非负权）中必须通过指定点的两个指定点之间的最短路径；（5）带权图（任意权）中最短路径问题，等等。2最短路径问题所谓最短路径问题（ShortestPa两个指定点之间的最短路径问题求解方法一：回溯法(从终点开始逐步逆向推算)主要步骤：先看与终点连接的结点，在结点上方写上该结点到终点的最短路线及权值；再将每个结点（与终点连接的结点）看成新的终点，以此类推，一直到起点为止。若在这过程中，一个结点同时与多个不同终点相连接，则该结点上方写上该结点到这些终点中最短的路线及权值；最终，起点上方的最短路线及权值即为起点到终点的最短路线及长度。3两个指定点之间的最短路径问题求解方法一：回溯法(从终点开始逐例使用回溯法求下图中结点1到结点10的最短路径3006-9-101508-101009-104005-8-102757-8-106002-6-9-105004-6-9-106003-5-8-106501-4-6-9-104例使用回溯法求下图中结点1到结点10的最短路径3006-9练习城市A到城市B的交通道路如下图所示，线上标注的数字为两点间距离(单位：万米)。某公司现需从A市紧急运送一批货物到B市。假设各条线路的交通状况相同，请为该公司寻求一条最佳路线。

3

7-B6

8-B8

4-7-B9

5-7-B10

6-8-B161-5-7-B172-5-7-B131-6-8-B18A-1-5-7-B5练习城市A到城市B的交通道路如下图所示，线上标注的数字为两指定点到其它所有点的最短路径解决这一问题最著名的方法是Dijkstra算法，这个算法是由荷兰计算机科学教授EdsgerW.Dijkstra在1959年提出的。他在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。6指定点到其它所有点的最短路径解决这一问题最著名的方法是DijDijkstra算法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算法原理如下：7Dijkstra算法Dijkstra算法是由Dijkstra算法的伪代码ProcedureDijkstra(G,W,a(,z))beginfori:=1tondol(vi):=l(a):=0S:=;//初始化标号及S，S用于保存已考察过的顶点的序列whileV(G)-S(zS)dobeginu:=不属于S且l(u)最小的一个顶点；

ifu为顶点zS:=S{u}；

elseS:=S{u}；for所有不属于S的顶点vdol(v):=min{l(v),l(u)+wuv}；endendDijkstra8Dijkstra算法的伪代码ProcedureDijkst例

用Dijkstra算法求下图中从a到所有其它结点的最短路径及长度。9例用Dijkstra算法求下图中从a到所有其它结点的最短路步骤uS

abcdez0-01a{a}0422c{a,c}03210123b{a,c,b}0328124d{a,c,b,d}032810145e{a,c,b,d,e}032810136z{a,c,b,d,e,z}03281013l(v):=min{l(v),l(u)+wuv}10步骤uS例

用Dijkstra算法求下图中从A到其它所有结点的最短路径及长度11例用Dijkstra算法求下图中从A到其它所有结点的最短路步骤uS

ABCDEFG0-01A{A}0712C{A,C}041543F{A,C,F}0411454114B{A,C,F,B}0411254115E{A,C,F,B,E}041125476G{A,C,F,B,E,G}04112547可以在Dijkstra算法的基础之上以如下方法找到最短路径：从终点往回走，找到它的前导顶点，使得它们之间的标号的差等于连接它们边的权重，如此下去直至到起点，从而找到一条最短路径。12步骤uS作业用Dijkstra算法求出下图中从顶点a到其它所有顶点的最短路径及及长度。13作业用Dijkstra算法求出下图中从顶点a到其它所有顶点有向图中求最短路径的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次循环结束。14有向图中求最短路径的Dijkstra算法设Sj是带权有向图G任意两点间的最短路径Floyd算法Warshall算法15任意两点间的最短路径Floyd算法15任意两点间的最短路径-Floyd算法首先定义两种矩阵运算：定义1

已知矩阵A=(aij)ml，B=(bij)l

n，规定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)16任意两点间的最短路径-Floyd算法首先定义两种矩阵运算：1例已知矩阵W，求WW17例已知矩阵W，求WW17例已知矩阵W，求WWcij=min(ai1+b1j,ai2+b2j,…,ail+blj)18例已知矩阵W，求WWcij=min(ai1+b1j,acij=min(ai1+b1j,ai2+b2j,…,ail+blj)19cij=min(ai1+b1j,ai2+b2j,…,ai任意两点间的最短路径-Floyd算法算法原理：若W=(wij)nn是图G的权矩阵，计算W[2]，W[3]，…，W[n]及S，其中W[k]=W[k-1]W=(wij[k])nn；

S=WW[2]W[3]

…W[n]=(sij)nn

。则wij[k]表示顶点i到顶点j经过k条边且权和最小的路径，sij表示顶点i到顶点j权和最小的路径（最短路径）。20任意两点间的最短路径-Floyd算法算法原理：20例求下图中任意两点间最短路径的长度。21例求下图中任意两点间最短路径的长度。212222由s16知，顶点v1到v6的最短路径为6；由s35知，顶点v3到v5的最短路径为2；由s45知，顶点v4到v5没有最短路径；23由s16知，顶点v1到v6的最短路径为6；23任意两点间的最短路径-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)；否则停止。24任意两点间的最短路径-Warshall算法算法原理：24例求下图中任意两点间最短路径的长度。wij

:=min(wij,wik+wkj)25例求下图中任意两点间最短路径的长度。wij:=min(wwij:=min(wij,wik+wkj)26wij:=min(wij,wik+wkj)262727Floyd算法的改进Floyd算法和Warshall算法只能给出任意两点间的最短路径的长度。改进的Warshall算法不仅能够给出任意两点间的最短路径的长度，同时也给出具体的最短路径。28Floyd算法的改进Floyd算法和Warsh改进后的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被访问的最后一个顶点，所以利用该矩阵可以重构最短路径。29改进后的Warshall算法算法原理：矩阵P中pij的值是最带负权图中的单源最短路径问题Dijkstra算法能够用于求带负权图中的指定两点间的最短路径？30带负权图中的单源最短路径问题Dijkstra算法能够用于求带例求下图中顶点a到c的最短路径。如果用Dijkstra算法，则求出的最短路径为ac，而不是abc。31例求下图中顶点a到c的最短路径。如果用Dijkstra算法带负权图中的单源最短路径问题Bellman-Ford算法该算法有一个限制条件，即要求图中不能包含权和为负值的回路。32带负权图中的单源最短路径问题Bellman-Ford算法32Bellman-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[v]=。distk[v]的生成：distk[v]=min{distk-1[v],min{distk-1[j]+wjv}}。33Bellman-Ford算法Bellman-Fo最短路径问题

(ShortestPathProblem)34最短路径问题

(ShortestPathProblem)最短路径问题所谓最短路径问题（ShortestPathProblem）就是在一个带权图中找出两点之间的最短路径（权和最小的路径）。最短路径问题通常有如下几种类型：（1）带权（非负权）图中两个指定点之间的最短路径；（2）带权图（非负权）中任意两点间的最短路径；（3）带权图（非负权）中从一个指定点到其它所有点的最短路径；（4）带权图（非负权）中必须通过指定点的两个指定点之间的最短路径；（5）带权图（任意权）中最短路径问题，等等。35最短路径问题所谓最短路径问题（ShortestPa两个指定点之间的最短路径问题求解方法一：回溯法(从终点开始逐步逆向推算)主要步骤：先看与终点连接的结点，在结点上方写上该结点到终点的最短路线及权值；再将每个结点（与终点连接的结点）看成新的终点，以此类推，一直到起点为止。若在这过程中，一个结点同时与多个不同终点相连接，则该结点上方写上该结点到这些终点中最短的路线及权值；最终，起点上方的最短路线及权值即为起点到终点的最短路线及长度。36两个指定点之间的最短路径问题求解方法一：回溯法(从终点开始逐例使用回溯法求下图中结点1到结点10的最短路径3006-9-101508-101009-104005-8-102757-8-106002-6-9-105004-6-9-106003-5-8-106501-4-6-9-1037例使用回溯法求下图中结点1到结点10的最短路径3006-9练习城市A到城市B的交通道路如下图所示，线上标注的数字为两点间距离(单位：万米)。某公司现需从A市紧急运送一批货物到B市。假设各条线路的交通状况相同，请为该公司寻求一条最佳路线。

3

7-B6

8-B8

4-7-B9

5-7-B10

6-8-B161-5-7-B172-5-7-B131-6-8-B18A-1-5-7-B38练习城市A到城市B的交通道路如下图所示，线上标注的数字为两指定点到其它所有点的最短路径解决这一问题最著名的方法是Dijkstra算法，这个算法是由荷兰计算机科学教授EdsgerW.Dijkstra在1959年提出的。他在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。39指定点到其它所有点的最短路径解决这一问题最著名的方法是DijDijkstra算法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算法原理如下：40Dijkstra算法Dijkstra算法是由Dijkstra算法的伪代码ProcedureDijkstra(G,W,a(,z))beginfori:=1tondol(vi):=l(a):=0S:=;//初始化标号及S，S用于保存已考察过的顶点的序列whileV(G)-S(zS)dobeginu:=不属于S且l(u)最小的一个顶点；

ifu为顶点zS:=S{u}；

elseS:=S{u}；for所有不属于S的顶点vdol(v):=min{l(v),l(u)+wuv}；endendDijkstra41Dijkstra算法的伪代码ProcedureDijkst例

用Dijkstra算法求下图中从a到所有其它结点的最短路径及长度。42例用Dijkstra算法求下图中从a到所有其它结点的最短路步骤uS

abcdez0-01a{a}0422c{a,c}03210123b{a,c,b}0328124d{a,c,b,d}032810145e{a,c,b,d,e}032810136z{a,c,b,d,e,z}03281013l(v):=min{l(v),l(u)+wuv}43步骤uS例

用Dijkstra算法求下图中从A到其它所有结点的最短路径及长度44例用Dijkstra算法求下图中从A到其它所有结点的最短路步骤uS

ABCDEFG0-01A{A}0712C{A,C}041543F{A,C,F}0411454114B{A,C,F,B}0411254115E{A,C,F,B,E}041125476G{A,C,F,B,E,G}04112547可以在Dijkstra算法的基础之上以如下方法找到最短路径：从终点往回走，找到它的前导顶点，使得它们之间的标号的差等于连接它们边的权重，如此下去直至到起点，从而找到一条最短路径。45步骤uS作业用Dijkstra算法求出下图中从顶点a到其它所有顶点的最短路径及及长度。46作业用Dijkstra算法求出下图中从顶点a到其它所有顶点有向图中求最短路径的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次循环结束。47有向图中求最短路径的Dijkstra算法设Sj是带权有向图G任意两点间的最短路径Floyd算法Warshall算法48任意两点间的最短路径Floyd算法15任意两点间的最短路径-Floyd算法首先定义两种矩阵运算：定义1

已知矩阵A=(aij)ml，B=(bij)l

n，规定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)49任意两点间的最短路径-Floyd算法首先定义两种矩阵运算：1例已知矩阵W，求WW50例已知矩阵W，求WW17例已知矩阵W，求WWcij=min(ai1+b1j,ai2+b2j,…,ail+blj)51例已知矩阵W，求WWcij=min(ai1+b1j,acij=min(ai1+b1j,ai2+b2j,…,ail+blj)52cij=min(ai1+b1j,ai2+b2j,…,ai任意两点间的最短路径-Floyd算法算法原理：若W=(wij)nn是图G的权矩阵，计算W[2]，W[3]，…，W[n]及S，其中W[k]=W[k-1]W=(wij[k])nn；

S=WW[2]W[3]

…W[n]=(sij)nn

。则wij[k]表示顶点i到顶点j经过k条边且权和最小的路径，sij表示顶点i到顶点j权和最小的路径（最短路径）。53任意两点间的最短路径-Floyd算法算法原理：20例求下图中任意两点间最短路径的长度。54例求下图中任意两点间最短路径的长度。215522由s16知，顶点v1到v6的最短路径为6；由s35知，顶点v3到v5的最短路径为2；由s45知，顶点v4到v5没有最短路径；56由s16知，顶点v1到v6的最短路径为6；23任意两点间的最短路径-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)；否则停止。57任意两点间的最短路径-Warshall算法算法原理：24例求下图中任意两点间最短路径的长度。wij

:=min(wij,wik+wkj)58例求下图中任意两点间最短路径的长度。wij:=min(wwij:=min(wij