最短路径和网络最大流问题.ppt

《最短路径和网络最大流问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节网络最短路径问题v1v2v3v4v5v6v7v8v9661021043264362231已知道路交通网络如下图，弧旁的数字表示通过这条道路所需要的时间。现某人要从v1出发到v8，求使总出行时间最小的路线。一、引例1问题的目标？v1v2v3v4v5v6v7v8v9661021043264362231——寻求上述赋权有向图D=（VE）中顶点V1至V8的一条路径P，路径P中所有边权之和W(a)

2、aP（总出行时间）最小。2基本概念1、网络：赋权有向图D=（V，E）；2、网络最短路径：（1）设P是网

3、络D=（VE）中从顶点vs到顶点vt一条路径，则称W(P)=W(a)

4、aP为路径P的权；（2）若P*为D=（VE）中从顶点vs到顶点vt的一条路径,而且W(P*)=Min{W(P)

5、P为D中顶点vs到顶点vt的路径}，则称P*为D中从vs到vt的最短路径。3广探法w6w2vw5w8w4w1w3w9w7w11w104深探法w6w2vw5w8w4w1w3w9w7w11w105一、Dijkstra算法一、算法的适用范围、主要功能和前提条件（一）适用范围——非负赋权有向图——设有向图D=（V，E），任

6、意aA,权W（a）0；（二）主要功能——求D=（V，E）中顶点v1至各点vj的最短路径Pj*及其长度W(Pj*)=d1j；6二、算法思想（一）最短路径的基本性质——最短路径的子路也为最短路径；设D中顶点v1至vj的最短路径Pj*=v1…vk…vivj其中，Pi*=v1…vk…vi必为D中顶点v1至vi的最短路，而且，W(Pj*)>=W(Pi*)d1j>=d1i7（二）搜寻方法——顶点标号法（1）T标号概念与方法：——临时性（Temporary)标号；（2）P标号概念与方法：——永久性（Perm

7、enent)标号；8三、算法步骤（1）给vs以P标号，P（vs）＝0，其余各点均给T标号，T（vi）＝+∞；（2）若vi点为刚得到P标号的点，考虑这样的点vj(vi,vj)属于E，且vj为T标号，对vj的T标号进行如下的更改：（3）比较所有具有T标号的点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则用代vi转回（2）。9例1狄克斯特拉算法08151012151131131011