资源描述：
《《最短路问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章最短路问题让我们先把最短路问题的提法明确一下§3.1什么是最短路问题1.求有向图上的最短路问题：设G=(V,A)是一个有向图，它的每一条弧ai都有一个非负的长度l(ai).在G中指定了两个顶点vs与vt,要求把从vs到vt并且长度最小的有向路找出来．2.求无向图上的最短(无向)路问题：设G=(V,E)是一个无向图，它的每一条弧ei都有一个非负的长度l(ei).在G中指定了两个顶点vs与vt,要求把连接vs与vt并且长度最小的(无向)路找出来．上面两个问题都可以称为最短路问题．很容易看出，这两个问题都有着大量
2、的生产实际背景.事实上，大至海、陆、空各种运输，小至一个人每天上班，都会遇到最短路问题.正因为它用处大，所以近二、三十年来国内外对这个问题进行了不少研究，也找到了许多比较好的计算方法.有趣的是，有些问题，从表面上看与最短路问题没有什么关系，却可以归结为最短路问题.下面就来举两个这样的例子：例1渡河问题：一个人带了一只狼、一只羊和一棵白菜想要过河,河上有一只独木船,每次除了人以外,只能带一样东西.另外,如果人不在旁时,狼就要吃羊,羊就要吃白菜.问应该怎样安排渡河,才能做到把所有东西都带过河去,而且在河上来回的次数又
3、最少.当然，这个问题不用图论也能解决．大家一眼就能看出，第一次应该带着羊过河，让狼和白菜留下,以下怎么渡法呢？下面就来讲一下怎样把这个问题转化成最短路问题．我们用M代表人，W代表狼，S代表羊，V代表白菜.开始时，设人和其他三样东西都在河的左岸，这种情况，我们用MWSV来表示.又例如人带了羊渡到河的右岸去了，这时左岸留下了狼和白菜，这种情况就用WV来表示.例如MWS表示人(M)狼(W)羊(S)在左岸而白菜(V)在右岸这种情况.那么总共可能有几种允许的情况呢如果不管狼是否吃羊、羊是否吃白菜，那么总共有16中情况，它们
4、分别是：MWSV,MWS,MWV,MSV,WSV,MW,MS,MV,WS,WV,SV,M,W,S,V,Ø(空集)例如MS表示人和羊在左岸，而狼和白菜在右岸；Ø表示左岸是空集，即人、狼、羊、白菜都已渡到右岸去了.检查一下就可以知道，这16种情况中有6种情况是不允许出现的.分别是：WSV,MW,MV,WS,SV,M.例如WSV表示狼、羊、白菜都在左岸而人在右岸，因为人不在旁边看着,狼就要吃羊，羊也要吃白菜；又如MV表示人和白菜在左岸，而狼和羊在右岸，当然也是不行的.因此，允许出现的情况只有10种.现在我们就来构造一个
5、图G，它的顶点就是这10种情况，G中的边是按照下述原则来连的；如果情况甲经过一次渡河可以变成情况乙，那么就在情况甲与乙之间连一条边.WVWSVØMWSMWVWSVMSMWSV例如，MWSV经过一次渡河可以变成WV(人带着羊过河，左岸留下狼和白菜)，又例如MWV经过一次渡河可以变为W(人带着白菜过河，留下狼)，或变为V.当然反过来，W也可以变为MWV(人带着白菜从右岸返回左岸).作出了图G以后，渡河问题就归结为下述问题了：“在图G中找一条连接顶点MWSV与Ø，并且包含边数最少的路”.如果我们设G的每条边的长度都是1
6、，那么也可以把渡河问题归结为：“找一条连接MWSV与Ø的最短路”.例2:某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升.现要将酒平分，求最少的操作次数.解设x1,x2,x3分别表示8,5,3升酒壶中的酒量.则容易算出(x1,x2,x3)的组合形式共24种.(0,5,3);(1,5,2);(1,4,3);(2,5,1);(2,4,2);(2,3,3);(3,5,0);(3,4,1);(3,3,2);(3,2,3);(4,4,0);(4,3,1);(4,2,2);(4,1,3);(5,3,0);(5,
7、2,1);(5,1,2);(5,0,3);(6,2,0);(6,1,1);(6,0,2);(7,1,0);(7,0,1);(8,0,0);于是问题转化为在该图中求(8,0,0)到(4,4,0)的一条最短路(求最短路的算法在有向图中仍适用).结果如下：每种组合用一个点表示，若点u能通过倒酒的方式变换为v,则u向v连有向边，并将各边赋权1，得一个有向赋权图.大家也许会认为，这两个例子本来就不很难，把它转化成图论问题，倒相当麻烦，有什么好处呢？其实这种做法还是很有好处的.因为在转化前，想解决这些问题，只能用凑的办法，或
8、者最多是凭经验.而转化成图论问题以后，就可以用一种系统的方法解决了.最后，还要指出一下，求最短有向路和求最短无向路这两个问题是密切关联的.下面将看到，求最短有向路的计算方法也可以用来求最短无向路.在这一章中，我们假设遇到的图G都是简单图.这样假设是合理的，因为如果G有平行弧或平行边，例如有好几条从vi到vj的弧，那么很显然，可以把这些弧中最短的一条留下，其余的都去掉，然后
