Dijkstra算法讲义.pptVIP

第七章 图论 7.4 最短路问题 例 7.4 最短路问题 Dijkstra算法 7.4 .1 Dijkstra算法 Dijkstra算法基本思想:把图中所有结点分为两组，每一个结点对应一个距离值。 第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度。 按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 procedure Dijkstra(G:所有权都为正数的加权连通简单图) {G带有顶点a＝v0,v1,…,vn＝z和权ω(vi,vj)，若(vi,vj)不是G的边，则ω(vi,vj)＝∞} for i:＝1 to n L(vi)＝∞ L(a):＝0 S:＝ （初始化标记，a的标记为0，其余结点标记为∞，S是空集} while z S begin u:＝不属于S的L(u)最小的一个顶点 S:＝S∪{u} for 所有不属于S的顶点v if L(u)＋ω(u,v)＜L(v) then L(v):＝L(u)＋ω(u,v) {这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记} end{L(z)＝从a到z的最短长度} 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 * 返回 结束 * 一位旅客要从A城到B城 他希望选择一条途中中转次数最少的路线； 他希望选择一条途中所花时间最短的路线； 他希望选择一条途中费用最小的路线； v5 v4 v3 v2 v1 v0 100 60 30 10 10 20 5 50 这些问题均是带权图上的最短路径问题。 边上的权表示一站 边上的权代表距离 边的权代表费用 Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。 荷兰计算机科学教授Edsger W.Dijkstra(1930-) 在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。 Dijkstra算法是求出一个连通加权简单图中从结点a到结点z的最短路。边(i,j)的权ω(i,j)＞0，且结点x的标号为L(x)。结束时，L(z)是从a到z的最短长度。 举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。 设源点为v0 初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点） 然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）： 若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值vm的距离值+Wmi），则要修改vi的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。 如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。 dij 下面给出该算法的框图： 通过框图，容易计算该算法计算量 。 下面通过一个实例来说明Dijkstra算法是如何工作的。 ∞ L(b)＋ω(b,d)＝3＋5＝8＜L(d) L(b)＋ω(b,e)＝3＋∞＝∞ u＝b，S＝{a,c,b} 3次迭代 L(b)＝3，L(d)＝10，L(e)＝12，L(z)＝∞ L(c)＋ω(c,b)＝2＋1＝3＜L(b) L(c)＋ω(c,d)＝2＋8＝10＜L(d) L(c)＋ω(c,e)＝2＋10＝12＜L(e) L(c)＋ω(c,z)＝2＋∞＝∞ u＝c，S＝{a,c} 2次迭代 L(b)＝4，L(c)＝2，L(d)＝L(e)＝L(z)＝∞ L(a)＋ω(a,b)＝0＋4＝4＜L(b) L(a)＋ω(a,c)＝0＋2＝