最短路问题PPT讲座.ppt

workAnalysis第六章最短路问题如何用最短的线路将三部电话连起来?此问题可抽象为设△ABC为等边三角形,连接三顶点的路线(称为网络)。这种网络有许多个,其中最短路线者显然是二边之和(如AB∪AC)。ABC最短路问题ABCP但若增加一个周转站(新点P),连接4点的新网络的最短路线为PA+PB+PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料,而且稳定性也更好。最短路问题问题描述: 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路. 有些问题,如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题,也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸,河上只有一条独木舟,每次除了人以外,只能带一样东西;另外,如果人不在,狼就要吃羊,羊就要吃白菜,问应该怎样安排渡河,才能做到既把所有东西都运过河去,并且在河上来回次数最少?这个问题就可以用求最短路方法解决。最短路问题定义:1)人—M(Man),狼—W(Wolf),羊—G(Goat),草—H(Hay)2)点——vi表示河岸的状态3)边——ek表示由状态vi经一次渡河到状态vj4)权——边ek上的权定为1我们可以得到下面的加权有向图最短路问题状态说明:v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二部图中求从v1到u1的最短路问题。v1v2v3v4v5u5u4u3u2u1最短路问题求最短路有两种算法:狄克斯屈拉(Dijkstra)标号算法逐次逼近算法最短路问题狄克斯屈拉(Dijkstra)标号算法的基本思路:若序列{vs,v1…..vn-1,vn}是从vs到vn间的最短路,则序列{vs,v1…..vn-1}必为从vs到vn-1的最短路。假定v1→v2→v3→v4是v1→v4的最短路,则v1→v2→v3一定是v1→v3的最短路,v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5最短路问题求网络图的最短路,设图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为(i,j)距离为dijP标号(点标号):b(j)—起点vs到点vj的最短路长;T标号(边标号):k(i,j)=b(i)+dij,步骤:;b(s)=0。={(i,j)}如果这样的弧不存在或vt已标号则计算结束;(i,j)=b(i)+(l),返回到第2步。