欢迎来到天天文库
浏览记录
ID:52509277
大小:375.82 KB
页数:11页
时间:2020-04-09
《最短路径和网络最大流问题.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第三节网络最短路径问题v1v2v3v4v5v6v7v8v9661021043264362231已知道路交通网络如下图,弧旁的数字表示通过这条道路所需要的时间。现某人要从v1出发到v8,求使总出行时间最小的路线。一、引例1问题的目标?v1v2v3v4v5v6v7v8v9661021043264362231——寻求上述赋权有向图D=(VE)中顶点V1至V8的一条路径P,路径P中所有边权之和W(a)
2、aP(总出行时间)最小。2基本概念1、网络:赋权有向图D=(V,E);2、网络最短路径:(1)设P是网
3、络D=(VE)中从顶点vs到顶点vt一条路径,则称W(P)=W(a)
4、aP为路径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、意aA,权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狄克斯特拉算法08151012151131131011
此文档下载收益归作者所有