《最短路径和网络最大流问题.ppt》由会员分享，可在线阅读，更多相关《最短路径和网络最大流问题.ppt（11页珍藏版）》请在金锄头文库上搜索。
1、第三节第三节 网络最短路径问题网络最短路径问题v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v8 8v v9 96 66 610102 210104 43 32 26 64 43 36 62 22 23 31 1 已知道路交通网络如下图，弧旁的数字表示已知道路交通网络如下图，弧旁的数字表示通过这条道路所需要的时间。现某人要从通过这条道路所需要的时间。现某人要从v v1 1出发出发到到v v8 8，求使总出行时间最小的路线。求使总出行时间最小的路线。一、引例一、引例1问题的目标？问题的目标？v v1 1v v2 2v v3 3v v4 4v v5 5v
2、v6 6v v7 7v v8 8v v9 96 66 610102 210104 43 32 26 64 43 36 62 22 23 31 1寻求上述赋权有向图寻求上述赋权有向图D=D=（V EV E）中顶点中顶点V V1 1至至V V8 8的一条路径的一条路径P P，路径路径P P中所有边权之和中所有边权之和W(a)|aW(a)|a P P（总出行时间）最小。总出行时间）最小。2基本概念基本概念1 1、网络网络：赋权有向图：赋权有向图D=D=（V V，E E）；）；2 2、网络最短路径网络最短路径： （1 1）设）设P P是网络是网络D=D=（V EV E）中从顶点中从顶点v vs s到顶
3、点到顶点v vt t 一条路径，则称一条路径，则称W(P)=W(P)= W(a)|aW(a)|aP P为为路径路径P P 的权的权； （2 2）若）若P P* *为为D=D=（V EV E）中从顶点中从顶点v vs s到顶点到顶点v vt t的的 一条路径一条路径, ,而且而且W(PW(P* *)=MinW(P)|P)=MinW(P)|P为为D D中顶中顶 点点v vs s到顶点到顶点v vt t的路径的路径 ，则称则称P P* *为为D D中从中从v vs s到到 v vt t的的最短路径最短路径。3广探法广探法w6w2vw5w8w4w1w3w9w7w11w104深探法深探法w6w2vw5w
4、8w4w1w3w9w7w11w105一、一、 DijkstraDijkstra算法算法一、算法的适用范围、主要功能和前提条件一、算法的适用范围、主要功能和前提条件（一）适用范围（一）适用范围 非负赋权有向图非负赋权有向图 设有向图设有向图D=D=（V V，E E），）， 任意任意a aA,A,权权W W（a a） 0 0；（二）主要功能（二）主要功能 求求D=D=（V V，E E）中顶点中顶点v v1 1至各点至各点v vj j的的 最短路径最短路径P Pj j* *及其长度及其长度W(PW(Pj j* *)=d)=d1j1j ；6二、算法思想二、算法思想（一）最短路径的基本性质（一）最短路径
5、的基本性质最短路径的子路也为最短路径；最短路径的子路也为最短路径； 设设D D中顶点中顶点v v1 1至至v vj j的最短路径的最短路径 P Pj j* * = = v v1 1 v vk k v vi i v vj j 其中，其中， P Pi i* * = = v v1 1 v vk k v vi i 必必为为D D中顶点中顶点v v1 1至至v vi i的最短路，而且，的最短路，而且， W(PW(Pj j* *)=W(P)=W(Pi i* *) ) d d1j 1j = d = d1i1i 7（二）搜寻方法（二）搜寻方法顶点标号法顶点标号法（1 1）T T标号概念与方法：标号概念与方法：
6、 临时性（临时性（Temporary)Temporary)标号；标号；（2 2）P P标号概念与方法：标号概念与方法： 永久性（永久性（PermenentPermenent) )标号；标号；8三、算法步骤三、算法步骤（1 1）给）给v vs s以以P P标号，标号，P P（v vs s）0 0，其余各点均给其余各点均给T T标号，标号， T T（v vi i）+；（2 2）若）若v vi i点为刚得到点为刚得到P P标号的点，考虑这样的点标号的点，考虑这样的点v vj j ( (v vi i, , v vj j) )属于属于E E，且，且v vj j为为T T标号，对标号，对v vj j的的T T标号标号 进行如下的更改：进行如下的更改：（3 3）比较所有具有）比较所有具有T T标号的点，把最小者改为标号的点，把最小者改为P P标号，标号， 即：即： 当存在两个以上最小者时，可同时改为当存在两个以上最小者时，可同时改为P P标号。标号。 若全部点均为若全部点均为P P标号则停止。否则用标号则停止。否则用 代代v vi i转转 回（回（2 2）。）。9例例1 1 狄克斯特拉算法狄克斯特拉算法 0 8151012151131131011
