资源描述：
《《最短路问题》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学(OperationsResearch)运筹帷幄之中决胜千里之外图与网络分析GraphTheoryandNetworkAnalysis第六章最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC最短路问题ABCP但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性
2、也更好。最短路问题问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题例6.4渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求
3、最短路方法解决。最短路问题定义：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最短路问题求最短路
4、有两种算法:狄克斯屈拉(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)距离为d
5、ijP标号(点标号)：b(j)—起点vs到点vj的最短路长；T标号(边标号)：k(i,j)=b(i)+dij，步骤：1.令起点的标号；b(s)＝0。2.找出所有vi已标号vj未标号的弧集合B={(i,j)}如果这样的弧不存在或vt已标号则计算结束；3.计算集合B中弧k(i，j)=b(i)+dij的标号4.选一个点标号在终点vl处标号b(l),返回到第2步。最短路问题例6.5求下图v1到v7的最短路长及最短路线①②③④⑤⑥⑦862523534210570862254411147510711P标号T标号9最短路问
6、题v1到v7的最短路长及最短路线如图所示：①②③④⑤⑥⑦86252353421057v7已标号，计算结束。从v1到v7的最短路长是11,最短路线：v1→v4→v6→v702411最短路问题从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。注：无向图最短路的求法只将上述步骤2将弧改成边即可。最短路问题例6.6求下图v1到各点的最短距离及最短路线。①②③④⑤⑥⑦⑧452617839326121618
7、0452231039612641166188122482418最短路问题v1到各点的最短距离及最短路线如图所示：①②③④⑤⑥⑦⑧45261783932612161802618所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。237184566134105275934682例6.7求从1到8的最短路径最短路问题237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4
8、=1p4=1p1=0最短路问题237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2最短路问题237184566134105275934682X={1,2,4}min{c16,c23,c25,c47}=min{0+3,2+6,
