《带权图的最短路径》PPT课件

《《带权图的最短路径》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、定义１设G＝(V,E)是简单图，若对于每一个e∈Ｅ，均有一正实数W(e)与之对应，则称W是G的权函数，并称G为带权图，记为G＝(V,E,W)。我们研究带权图，一个重要的内容就是寻找某类具有最小（最大）权的子图，其中之一就是最短路问题，例如：给定一个连接各城市的铁路网络（连通的带权图），在这个网络中的两个指定的城市之间确定一条最短路。定义２设G＝(V,E,W)是带权图，μ＝(ei1,ei2,……eik)是G中的一条路，μ的路长为W(μ)＝∑W(ei)。从u到v的最短路P是指满足下列条件的路W(P)＝min{W(μ)

2、μ为从u到v的路}

3、由上述定义可以看到，如果每条边的权函数值为1，则带权图的路长与一般图的路长是一致的。§５带权图的最短路径求最短路长的算法是E.W.Dijkstra于1959年提出来的，这是至今公认的求最短路长的最好算法，我们称它为Dijkstra算法。Dijkstra算法功能：在连通的带权图中，求从v0到v的最短路的路长。No1.p0＝v0；P＝{v0}；T＝V{v0};d(p0)＝0；(t∈T)(d(t)＝∞)；No2.(t∈T)(d(t)＝min(d(t)，d(p0)+W(p0,t))；No3.在T中选取t0,使(t∈T)(d(t0)≤

4、d(t))；No4.p0＝t0；P＝P{t0}；T＝T{t0}；No5.ifp0≠vthengotoNo2elseend。例1.求图1中从v0到v5的最短路径.1.p0＝v0,P＝{v0},T＝{v1,v2,v3,v4,v5}d(p0)＝0,d(v1)＝d(v2)＝d(v3)＝d(v4)＝d(v5)＝∞.2.d(v1)＝1,d(v2)＝4,d(v3)＝d(v4)＝d(v5)＝∞.3.t0＝v14.p0＝t0＝v1,P＝{v0,v1},T＝{v2,v3,v4,v5}.5.p0≠v5,GoTo2.2.d(v2)＝3,d(v3)＝8,

5、d(v4)＝6,d(v5)＝∞.3.t0＝v24.p0＝t0＝v2,P＝{v0,v1,v2},T＝{v3,v4,v5}5.p0≠v5,GoTo2.v0v2v1v3v4v51425713262.d(v3)＝8,d(v4)＝4,d(v5)＝∞.3.t0＝v4.4.p0＝t0＝v4,P＝{v0,v1,v2,v4},T＝{v3,v5}.5.p0≠v5,GoTo2.2.d(v3)＝7,d(v5)＝10.3.t0＝v34.p0＝t0＝v3,P＝{v0,v1,v2,v3,v4},T＝{v5}5.p0≠v5,GoTo2.2.d(v5)＝9.3.t0

6、＝v5.4.p0＝t0＝v5,P＝{v0,v1,v2,v3,v4,v5},T＝{}.5.p0＝v5.Dijkstra算法的基本思想是：将图G中结点集合V分成两部分，一部分称为具有P标号的集合，另一部分称为具有T标号的集合。所谓结点ａ的P标号是指从v0到ａ的最短路的路长，而结点ｂ的Ｔ标号是指从v0到ｂ的某条路径的长度。Dijkstra算法中首先将v0取为P标号结点，其余的点均为T标号结点，然后逐步地将具有T标号的结点改为P标号结点，当结点v也被改为P标号时，就找到了从v0到v的最短路径的长度。§6Euler图Euler图的来历为kon

7、igsberg七桥问题。定义1设G＝(V,E)是无向连通图。1)若存在一条路P，此路通过G中每条边且仅一次，则称此路为Euler路。2)若存在一圈C，此圈通过G中每条边一次且仅一次，则称此圈为Euler圈。3)若G中有Euler圈，则称G为Euler图。这类通过各边恰好一次的问题就是通常所说的一笔画问题（即笔不离纸，线不重复）。定理1设G＝(V,E)是无向连通图，那么，G是Euler图当且仅当G中每个结点都是偶结点。例1图G如图所示，问图G是否为Euler图，若是，求出其Euler圈。由于G中的六个结点均为偶结点且G连通，根据Eul

8、er定理可知，G为Euler图，仿照定理证明的办法，可得到G中的Euler圈。具体步骤如下：123456在图中任意找一简单圈C＝(1,2,3,1)，发现还有7条边不在此圈中，边{3,4}不在C中且与圈中的结点3相关联。由结点3出发经过边{3,4}可得一简单圈C＝(3,4,5,3)，将C并入C得到一个新的更长的简单圈C＝(1,2,3,4,5,3,1)。此时仍有4条边不在C中，边{4,6}不在C中且与结点4关联。由结点4出发经过边{4,6}又可得到一简单圈C＝(4,6,5,2,4)，将C并入C得到一个更长的简单圈C＝(1,2

9、,3,4,6,5,2,4,5,3,1)。由于G中所有的边都已在C中，故知此圈C为G中的一个Euler圈。例2．在哥尼斯堡七桥问题中，由于每个结点均为奇结点，故由Euler定理的充要条件知，该图中不存在经过每条边一次且仅一次的Euler