最短路径问题.ppt

1、1，最短路径问题，2，最短路径问题，所谓的最短路径问题是在一个加权图中寻找两点之间的最短路径(加权和最小路径)。通常有几种类型的最短路径问题：(1)加权(非负)图中两个指定点之间的最短路径；(2)加权图中任意两点之间的最短路径(非负权重)；(3)从指定点到加权图中所有其他点的最短路径(非负权重)；(4)加权图中必须通过指定点的两个指定点之间的最短路径(非负权重)；(5)加权图中的最短路径问题(任意权重)，等等。3、两个指定点之间的最短路径问题，求解方法1:回溯法(从终点一步一步向后计算)主要步骤：首先查看与终点相连的节点，并写出从该节点到该节点上方的终点的最短路径和权重；然后将每个节点(与端点

2、相连的节点)视为新的端点，依此类推，直到起始点。如果一个节点在此过程中同时与多个不同的端点相连，请写出从该节点到该节点上方的这些端点的最短路径和权重；最后，起点以上的最短路线和重量是从起点到终点的最短路线和长度。4、本例使用回溯法寻找下图中从节点1到节点10的最短路径，5、练习下图所示的从城市A到城市B的交通道路，该线上标记的数字是两点之间的距离(单位：10，000米)。一家公司急需将一批货物从A市运输到B市。假设所有路线的交通状况相同，请为公司找到最佳路线。6，指定所有其他点的最短路径。解决这个问题最著名的方法是迪杰斯特拉算法，它是由荷兰计算机科学教授埃德格迪杰斯特拉于1959年提出的。19

3、72年，他获得了美国计算机协会颁发的图灵奖，这是计算机科学领域最负盛名的奖项之一。7、Dijkstra算法，Dijkstra算法是从近到远逐步寻找从源点到任何其他点的最短路径。假设G=是一个连通加权简单图，G中的顶点是v0，v1，vn。假设v0是起点，边(vi，vj) (or)的权重是wij。如果(vi，vj) (or)不是图中的边，则权重为wij=，标签l(x)表示从v0到X。那么Dijkstra算法的原理如下：8、Dijkstra算法的伪代码，过程Dijkstra (g，w，a(，z)开始于I :=1到n do l(VI):=l(a):=0s 3360=；/初始化标签和s，s用于保存研究的

4、顶点序列，而v (g)-s (zs) dobegin u3360=不属于s且具有最小l(u)的顶点；如果u是顶点z，S:=苏；否则S:=苏；对于不属于s v的所有顶点，l (v) :=minl (v)，l(u)wuv；例如，结束Dijkstra，9，使用Dijkstra算法在下图中找到从A到所有其他节点的最短路径和长度。例如，步骤u a b c d e Z 0-01 a 0 42 c a，c 0 32 10 12 3b a，c，b 0 32 8 12 4d a，c，b，d 0 32 8 10 14 5e a，c，b，d，e 0 32 8 10 13 6 z a，c，b，d，Z 0 328 10

5、 13，l (v) :=minl (v)，l (u) wuv，11， 使用Dijkstra算法找到从a到下图中所有其他节点的最短路径和长度，12，步骤u a b C d e f g 0-01 a 0 71 2c a，c 0 41 54 3f a，C，f 0411454114b a，C，f，b 0411254115e a，C，f，b，e 041125476g a，C，f，b，e，g 04112547，基于13岁。下图中从顶点A到所有其他顶点的最短路径和长度是通过Dijkstra算法获得的。求有向图中最短路径的Dijkstra算法，设Sj为加权有向图中从顶点1到顶点j的最短有向路径的长度。步骤1:

6、设置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。第三步：将t中的每个点j设置为Sj=最小Sj，Sk wkj，然后转到第二步。该算法在n-1个周期后结束。15，任意两点之间的最短路径，Floyd算法Warshall算法，16，任意两点之间的最短路径-Floyd算法，首先，定义两种矩阵运算：定义1个已知矩阵A=(aij)ml，B=(bij)l n，并指定C=AB=(cij)mn，其中CIJ=min (AI1B1J，所有blj)定义了2个已知矩阵A=(aij)m n，B=(bi

7、j)mn，并规定，C=AB=(dij)mn，其中dij=min(aij，bij)，17，例如，已知矩阵w，找到ww，18，例如，已知矩阵w，找到WW，cij=min(。Cij=min (ai1b1j，ai2b2j，ailblj)，20，任意两点之间的最短路径-Floyd算法，算法原理：如果W=(wij)nn是图g的权重矩阵，计算W2，W3，Wn和s，其中wk=wk-1w=(wijk)nn；S=WW2 W3 Wn=(sij)nn .Wijk表示从顶点I到顶点j通过k条边的路径，加权和最小，sij表示从顶点I到顶点j的路径，加权和最小(最短路径)。例如，21，在下图中找到任意两点之间的最短路径长度

8、。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，wiwkj)，j=1，2，n；(5)i:=i 1，如果在，转到(4)；(6)k:=k 1，如果kn，转到(3)；否则停止。例如，25，在下图中找到任意两点之间的最短路径长度。wij3360=min (wij，wiwkj)，26，wij:=min (wij，wiwkj)，

9、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:=最小值(wij，wiwkj)，j=1，2和n；pij=pkj，j=1，2，n；(5)i:=i 1，如果在，转到(4)；(6)k:=k 1，如果kn，转到(3)；否则停止。矩阵p中pij的值是最短路径上从

10、I到j的最后一个顶点，因此可以用这个矩阵来重构最短路径。30，负权图中的单源最短路径问题。Dijkstra算法可用于寻找负权图中指定两点之间的最短路径。例如，31，在下图中找到从顶点A到C的最短路径。如果使用Dijkstra算法，最短路径是ac，而不是abc。32，负权图中的单源最短路径问题，Bellman-Ford算法该算法有一个限制条件，即它要求图不能包含负权环。Bellman-Ford算法，Bellman-Ford算法的目的是构造最短路径长度数组序列dist1v，dist2v，distn-1v，其中dist1v表示从起点u到图中所有其他顶点v的仅一条边的长度，distkv表示从起点u到最多通过k条边的顶点v的最短路径长度。贝尔曼-福特算法的最