《网络分析最短路和最大流问题课件.ppt》由会员分享，可在线阅读，更多相关《网络分析最短路和最大流问题课件.ppt（56页珍藏版）》请在三一办公上搜索。
1、,63最短路问题P问题描述就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路有些问题,如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题,也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用,最短路问题Page 2例渡河游戏老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸,河上只有一条独木舟,每次除了人以外,只能带样东西;另外,如果人不在,狼就要吃羊,羊就要吃白菜,问应该怎样安排渡河,才能做到既把所有东西都运过河去,并且在河上来回次数最少?这个问题就可以用求最短路方法解决。,最短路问题Page 3定义1)人-M(Man),狼W(wof),羊G(
2、Goat)草一H(Hay)2)点V1表示河岸的状态3)边表示由状态v经一次渡河到状态v4)权边ek上的权定为1我们可以得到下面的加权有向图,最短路问题Page 4状态说明:v1pu1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,w,H);VaU=(M,G, Vs,us =(M,G)此游戏转化为在下面的二部图中求从v1到u1的最短路问题。(M, W,G, H)(M,W,G)(M, W,H)(M,G, H)M,G)(M, G, H(M, W,H)(M, W,G)(M,w,H),最短路问题Page 5迪科斯彻(迪杰斯特拉 Dijkstra)标号算法的基本思路:若序列vVmVn是
3、从v到v间的最短路,则序列v1vn必为从v到v的最短路。假定v1V2V3V4是V1V的最短路,则v1V3一定是v1v3的最短路,V2V3V4也一定是v2V4的最短路。,最短路问题Page 6求网络图的最短路,设图的起点是v,终点是v,以v为起点v为终点的边记为(,距离为dLy-起点到点的最短路长;k(j)=L+diDijkstra算法步骤从s点出发,因L=0并将Ls的值标注在s点旁的小方框内。表示点已标注。从s点出发,找出与s点相邻的所有的点,记为点集V1,取vst,L=mineLs+d刚将r点标注,并将L的值标注在r点旁的小方框内。从已标注的点出发,找出与这些点相邻的所有未标注的点将点标注,
4、并将L的值标注在点旁的小方概n,则记为点集V2,取v,St.,1s=mmneLs+d重复第三步,一直到点得到标号为止,它旁边的小方框表的数值就是s点到t点的最小距离。,最短路问题Page 7例3求下图v到v7的最短路长及最短路线v7已标号,计算结束。从v到v7的最短路长是10,最短路线:v1V3v6VsV7,最短路问题Page 9从上例知,只要某点已标号,说明已找到起点v到该点的最短路线及最短距离,因此可以将每个点标号,求出v到任意点的最短路线,如果某个点不能标号,说明,不可达,最短路问题Page 10例31求下图v到各点的最短距离及最短路线。0(122所有点都已标号,点上的标号就是v1到该点的最短距离,最短路线就是红色的链。,最短距离的矩阵算法Page 11网络图的矩阵表示d,d1表示点到点两相邻点间的B距离,若点不相邻,则d1=V,
