nullnull最短路问题 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。求最短路有两种算法，一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法；另一种是求网图上任意两点之间最短的矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .null渡河问题 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。设：M—人
W—狼
S—羊
V—白菜渡河方案共有10种，构造如下一个图，每条边的距离为1，问题变为求一条从MWSV到φ的最短路。北岸南岸null狄克斯屈拉(Dijkstra)标号算法点标号：b(j) —起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+dij，步骤：1.令起点的标号；b(s)＝0。先求有向图的最短路，设网络图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为dij 2.找出所有vi已标号vj未标号的弧集合 B=｛ （i，j） ｝如 果这样的弧不存在或vt已标号则计算结束；3.计算集合B中弧k(i，j)=b(i)+dij的标号4.选一个点标号
返回到第2步。null【例】求下图v1到v7的最短路长及最短路线086225441114751071211v7已标号，计算结束。从v1到v7的最短路长是 11最短路线是：v1 v4 v6 v7null从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj .无向图最短路的求法无向图最短路的求法只将上述步骤2改动一下即可。点标号：b(i) —起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+dij，步骤：1.令起点的标号；b(s)＝0。3.计算集合B中边标号：k[i，j]=b(i)+dij4.选一个点标号:
返回到第2步。 2.找出所有一端vi已标号另一端vj未标号的边集合 B=｛ [i，j] ｝如果这样的边不存在或vt已标号则计算结束；null【例】求下图v1到各点的最短路及最短距离0452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。进入演示和练习null有负权的最短路算法假设图中没有负回路。如下图是一条负回路，最短路权无下界。当vi到vj之间没有弧连接时，令wij＝＋∞列表迭代计算：设vs到vj经过vi到达vj，则vs到vj的最短距离为：迭代：null【例】求下图v1到v8的最短路长及最短路线null－5－2－71－150－5－2－7－3－1－560－5－2－7－3－1－56nullnull**任意两点间最短距离的矩阵算法**（选讲）【例】在下图中用矩阵计算法求各点之间的最短距离 【解】定义dij为图中两相邻点的距离，若i与j不相邻，令dij=∞。则null步骤:1. null应用（教材P270例4）161617171822304159223041233123最优更新方案：1.第一年和第三年购置新设备；2.第一年和第四年购置新设备。总费用为53。null最大流问题作业：教材P284 10.6 10.7 10.9 10.8* 10.10*1.理解点标号和弧（边）标号的含义
2.掌握一个点到其它任意点最短路的求法
3.掌握无向图的最短路的求法进入练习
本文档为【ch7-3】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483