第七章 最短路径问题.ppt

最短路径问题(Shortest Path Problem) 最短路径问题 所谓最短路径问题（Shortest Path Problem）就是在一个带权图中找出两点之间的最短路径（权和最小的路径）。 最短路径问题通常有如下几种类型： （1）带权（非负权）图中两个指定点之间的最短路径； （2）带权图（非负权）中任意两点间的最短路径； （3）带权图（非负权）中从一个指定点到其它所有点的最短路径； （4）带权图（非负权）中必须通过指定点的两个指定点之间的最短路径； （5）带权图（任意权）中最短路径问题，等等。 两个指定点之间的最短路径问题 求解方法一：回溯法(从终点开始逐步逆向推算) 主要步骤： 先看与终点连接的结点，在结点上方写上该结点到终点的最短路线及权值； 再将每个结点（与终点连接的结点）看成新的终点，以此类推，一直到起点为止。若在这过程中，一个结点同时与多个不同终点相连接，则该结点上方写上该结点到这些终点中最短的路线及权值； 最终，起点上方的最短路线及权值即为起点到终点的最短路线及长度。 例 使用回溯法求下图中结点1到结点10的最短路径 练习 城市A到城市B的交通道路如下图所示，线上标注的数字为两点间距离(单位：万米)。某公司现需从A市紧急运送一批货物到B市。假设各条线路的交通状况相同，请为该公司寻求一条最佳路线。 指定点到其它所有点的最短路径 解决这一问题最著名的方法是Dijkstra算法，这个算法是由荷兰计算机科学教授Edsger W.Dijkstra在1959年提出的。 他在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。 Dijkstra算法 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算法原理如下： Dijkstra算法的伪代码 Procedure Dijkstra(G, W, a (,z)) begin for i:=1 to n do l(vi):=? l(a):=0 S:=?; //初始化标号及S，S用于保存已考察过的顶点的序列 while V(G)-S?? (z?S) do begin u:=不属于S且l(u)最小的一个顶点； if u为顶点z S:=S?{u}； else S:=S?{u}； for 所有不属于S的顶点v do l(v):=min{l(v), l(u)+wuv}； end end Dijkstra 例 用Dijkstra算法求下图中从a到所有其它结点的最短路径及长度。 步骤 u S a b c d e z 0 - ? 0 ? ? ? ? ? 1 a {a} 0 4 2 ? ? ? 2 c {a,c} 0 3 2 10 12 ? 3 b {a,c,b} 0 3 2 8 12 ? 4 d {a,c,b,d} 0 3 2 8 10 14 5 e {a,c,b,d,e} 0 3 2 8 10 13 6 z {a,c,b,d,e,z} 0 3 2 8 10 13 步骤 u S A B C D E F G 0 - ?