图论-4(最短路问题)

《图论-4(最短路问题)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图论引言7.1图的基本概念7.2路与连通7.3图的矩阵表示7.4最短路径问题7.5图的匹配8.1Euler图和Hamilton图8.2树8.3生成树8.4平面图7.4最短路问题一、问题的提出赋权图（网络）：G=(V,E)中，给每条边a=赋予一个非负实数权wij，得到一个有向网络7.4最短路问题路径路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和[距离矩阵]对上述网络，定义D=(dij)nn，n=

2、V

3、wij当Edij=其它[带权路径长度]对上述网络，路径v1,v2

4、,…,vk的带权路径长度定义为7.4最短路问题最短路问题在实际工作中应用1、通讯网络中最可靠问题2、最大容量问题3、统筹方法中求关键路线4、背包问题5、选址问题6、工件加工顺序问题7、中国邮递员问题背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。7.4最短路问题例一位旅客要从A城到B城他希望选择一条途中中转次数最少的路线；他希望选择一条途中所花时间

5、最短的路线；他希望选择一条途中费用最小的路线；v5v4v3v2v1v01006030101020550这些问题均是带权图上的最短路径问题。边上的权表示一站边上的权代表距离边的权代表费用7.4最短路问题Dijkstra算法Floyd算法Floyd-Warshall算法7.4最短路问题Dijkstra算法Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。荷兰计算机科学教授EdsgerW.Dijkstra(1930

6、-)在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。Dijkstra算法是求出一个连通加权简单图中从结点a到结点z的最短路。边(i,j)的权ω(i,j)＞0，且结点x的标号为L(x)。结束时，L(z)是从a到z的最短长度。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。7.4.1Dijkstra算法Dijkstra算法基本思想:把图中所有结点分为两组，每一个结点对应一个距离值。第一组：包括已确定最短路径的结点，结点对应的距离值是由

7、v0到此结点的最短路径长度；第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度。按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。7.4.1Dijkstra算法设源点为v0初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一

8、组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值>vm的距离值+Wmi），则要修改vi的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。7.4.1Dijkstra算法procedureDijkstra(G:所有权都为正数的加权连通简单图){G带有顶点a

9、＝v0,v1,…,vn＝z和权ω(vi,vj)，若(vi,vj)不是G的边，则ω(vi,vj)＝∞}fori:＝1tonL(vi)＝∞L(a):＝0S:＝（初始化标记，a的标记为0，其余结点标记为∞，S是空集}whilezSbeginu:＝不属于S的L(u)最小的一个顶点S:＝S∪{u}for所有不属于S的顶点vifL(u)＋ω(u,v)＜L(v)thenL(v):＝L(u)＋ω(u,v){这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记}end{L(z)＝从a到z的最短长度}dij7.4.1Dijkstra算法下面给出该算法的

10、框图：通过框图，容易计算该算法计算量。7.4.1Dijkstra算法下面通过一个实例来说明Dijkstra算法是如何工作的。∞7.4.1Dijkstra算法7.4.1Dijkst