资源描述：
《运筹学_最短路问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§3最短路问题试探性标号(tentativelabel),永久性标号(permanentlabel)T(vj)=min[T(vj),P(vi)+lij]⑶比较所有具有T标号的点,最小者改为P标号。Dijkstra算法(不含负权边)⑴给vi以P标号,P(vi)=0,其余各点均给T标号,T(vi)=+∞⑵与刚获P标号点vi以相邻只有T标号各点vj改进：P(vi)=min[T(vj)]并列最小者,同时改为P标号。若全部点均为P标号则停；否则用vi代vi,转⑵.例3用Dijkstra算法求v1点到v7点的
2、最短路。0v5746167v4v7v2v65223v3v122567100v5746167v4v7v2v65223v3v1220v5746167v4v7v2v65223v3v12520v5746167v4v7v2v65223v3v126520v5746167v4v7v2v65223v3v1276520v5746167v4v7v2v65223v3v12v177例9用Dijkstra算法⑴P(v1)=0,余皆为T标号:T(vi)=+∞(i=2,…,8)求v1点到v8点的最短路。⑵T(v2)=min(T
3、(v2),P(v1)+l12)=min(+∞,0+4)=4T(v3)=min(T(v2),P(v1)+l13)=min(+∞,0+6)=6⑶P(v2)=4,(v1,v2)⑸P(v3)=6,(v1,v3)⑷T(v4)=min(T(v4),P(v2)+l24)=min(+∞,4+5)=9T(v5)=min(T(v5),P(v2)+l25)=min(+∞,4+4)=8⑹T(v4)=min(T(v4),p(v3)+l34)=min(6,6+4)=9,T(v5)=min(T(v5),P(v3)+l35)=m
4、in(8,6+7)=8v5746167v4v7v2v65223v3v12P158类例4求图中任意两点间的最短路。dij为两相邻点的距离，是从i到j点的直接距离。D(0)=5022∞5003∞624∞4110422028∞0210158v44226v2v5v1423v3所以我们先考虑与之间有一个中间点的情况.从i到j点的最短距离不一定是i→j,i→l→k→j,可能是i→l→j,n个点的网络,i到j的最短距离经过的中间点最多有n-2个或i→l→…→k→j,P158类例4求图中任意两点间的最短路。求v1
5、→v2的最短距离为,具体操作是把第i行和转置后的第j列相加,从中找出最小者.D(0)=5022∞5003∞624∞4110422028∞0210158v44226v2v5v1423v3所以我们先考虑i与j之间有一个中间点的情况min{d11+d12,d12+d22,d13+d32,d14+d42,d15+d52}r应经过网络的每一点,或网络中的每一点都要作中间点.即min{dir+dr2}r=1,2,…,n55∞4∞0512∞503∞2d12(1)=4第一行转置后的第二列P158类例4求图中任意两
6、点间的最短路。051∞2052∞20103∞4051∞25032∞554∞∞051∞21100461151∞8051∞22∞2402∞3∞2051∞2∞2804∞79∞6052∞250102∞5032∞100134∞110046610106∞2∞2407∞126∞∞2804∞2182∞50102∞50102∞50102∞50102∞5512∞∞052∞2230825032∞73310∞11004631301282∞2404∞2122∞2804∞588623082230822308223082282
7、∞4052∞22∞6405032∞7∞96∞1100463∞6862∞2404∞880∞2804∞∞14442∞6402∞6402∞6402∞6402∞8∞2052∞2∞24045032∞∞27∞∞110046∞1244102∞240∞∞644∞2804∞41208∞2404∞2404∞2404∞2404∞76∞6P158类例4求图中任意两点间的最短路。051∞25032∞554∞∞5032∞100134∞50102∞5032∞73310∞230825032∞7∞96∞2∞6405032∞∞27∞
8、∞∞2404051∞21100461151∞8110046610106∞50102∞1100463130128230821100463∞6862∞640110046∞124410∞2404051∞22∞2402∞3∞22∞2407∞126∞50102∞2∞2404∞2122230822∞2404∞8802∞6402∞240∞∞644∞2404051∞2∞2804∞79∞6∞2804∞2182∞50102∞∞2804∞588623082∞2804∞∞14442∞640∞2804∞41
