图论最短路问题

图论最短路问题第一页，共三十六页，编辑于2023年，星期二7.4最短路问题一、问题的提出

赋权图（网络）：G=(V,E)中，给每条边a=<vi,vj>赋予一个非负实数权wij

，得到一个有向网络第二页，共三十六页，编辑于2023年，星期二7.4最短路问题路径路径长度

非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和[距离矩阵]

对上述网络，定义D=(dij)nn，n=|V|

wij

当<vi,vj>E

dij=其它[带权路径长度]

对上述网络，路径v1,v2,…,vk的带权路径长度定义为第三页，共三十六页，编辑于2023年，星期二7.4最短路问题最短路问题在实际工作中应用1、通讯网络中最可靠问题2、最大容量问题3、统筹方法中求关键路线4、背包问题5、选址问题6、工件加工顺序问题7、中国邮递员问题背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

第四页，共三十六页，编辑于2023年，星期二7.4最短路问题例一位旅客要从A城到B城他希望选择一条途中中转次数最少的路线；他希望选择一条途中所花时间最短的路线；他希望选择一条途中费用最小的路线；v5v4v3v2v1v0

1006030101020

550这些问题均是带权图上的最短路径问题。边上的权表示一站边上的权代表距离边的权代表费用第五页，共三十六页，编辑于2023年，星期二7.4最短路问题Dijkstra算法Floyd算法Floyd-Warshall算法第六页，共三十六页，编辑于2023年，星期二7.4最短路问题Dijkstra算法

Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

荷兰计算机科学教授EdsgerW.Dijkstra(1930-)在1972年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。Dijkstra算法是求出一个连通加权简单图中从结点a到结点z的最短路。边(i,j)的权ω(i,j)＞0，且结点x的标号为L(x)。结束时，L(z)是从a到z的最短长度。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。

第七页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法Dijkstra算法基本思想:把图中所有结点分为两组，每一个结点对应一个距离值。第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度；第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度。按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。第八页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法设源点为v0初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）

然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值>vm的距离值+Wmi），则要修改vi的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。第九页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法procedureDijkstra(G:所有权都为正数的加权连通简单图){G带有顶点a＝v0,v1,…,vn＝z和权ω(vi,vj)，若(vi,vj)不是G的边，则ω(vi,vj)＝∞}fori:＝1tonL(vi)＝∞L(a):＝0S:＝（初始化标记，a的标记为0，其余结点标记为∞，S是空集}while

zS

beginu:＝不属于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的最短长度}

dij第十页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法下面给出该算法的框图：通过框图，容易计算该算法计算量。第十一页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法下面通过一个实例来说明Dijkstra算法是如何工作的。∞第十二页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法第十三页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法

0次迭代

L(a)＝0L(b)＝L(c)＝L(d)＝L(e)＝L(z)＝∞S＝1次迭代u＝a，S＝{a}L(a)＋ω(a,b)＝0＋4＝4＜L(b)L(a)＋ω(a,c)＝0＋2＝2＜L(c)L(a)＋ω(a,d)＝0＋∞＝∞L(a)＋ω(a,e)＝0＋∞＝∞L(a)＋ω(a,z)＝0＋∞＝∞L(b)＝4，L(c)＝2，L(d)＝L(e)＝L(z)＝∞2次迭代u＝c，S＝{a,c}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＋∞＝∞L(b)＝3，L(d)＝10，L(e)＝12，L(z)＝∞3次迭代u＝b，S＝{a,c,b}L(b)＋ω(b,d)＝3＋5＝8＜L(d)L(b)＋ω(b,e)＝3＋∞＝∞145623108abcdez用Dijkstra算法求a和z之间最短路所用的步骤。L(b)＋ω(b,z)＝3＋∞＝∞L(d)＝8，L(e)＝12，L(z)＝∞4次迭代u＝d，S＝{a,c,b,d}L(d)＋ω(d,e)＝8＋2＝10＜L(e)L(d)＋ω(d,z)＝8＋6＝14＜L(z)L(e)＝10，L(z)＝145次迭代u＝e，S＝{a,c,b,d,e}L(e)＋ω(e,z)＝10＋3＝13＜L(z)L(z)＝13结束u＝z，S＝{a,c,b,d,e,z}从a到z的最短路的长度为13。第十四页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法Dijkstra算法(另外一种说明)求有向网络G=(V,A)中结点v1

到其它结点的最短距离。设D为G的距离矩阵，n=|V|，向量U=(u1,u2,…,un)的ui

标记结点v1到vi

的距离。

S为已取得最短路的结点集合，其中每个结点在U中有固定标号标记取得的最短路的长度；S为未取得最短路的结点集合，其中每个结点在U中有临时标号。第十五页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法0.初始化：u1(1)

0，uj(1)d1j(j=2,3,…,n)S(1)

{v1}，S(1)

{v2

,v3

,…

,vn}，m=1;1.选固定标号：在S(m)中求vk，使得uk(m)=min{uj(m)|vjS(m)}。若uk(m)=，则S(m)中的结点无最短路径；否则转2。2.判结束：令S(m+1)

S(m)

{vk},S(m+1)

S(m)

{vk}

若m=n1，结束。3.修改临时标号：对所有vjS(m+1)

，令

uj(m+1)=min{uj(m)

,uk(m)+dkj}，m

m+1；转1。第十六页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法Dijkstra算法只求出图中一个特定的顶点到其他各定点的最短路。但在许多实际问题中，需求出任意两点之间的最短路，如全国各城市之间最短的航线，选址问题等。当然，要求出一个图的任意两点间的最短距路，只需将图中每一个顶点依次视为始点，然后用Dijkstra算法就可以了。Dijkstra算法在物流配送中的应用OSPF（openshortestpathfirst,开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。第十七页，共三十六页，编辑于2023年，星期二7.4.1Dijkstra算法Dijkstra算法要求图上的权是非负数，否则结果不正确；Dijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。利用求最短路的方法求最长路。由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，必须采用Floyd算法--动态规划算法Floyd算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.第十八页，共三十六页，编辑于2023年，星期二7.4.2Floyd算法如果有一个矩阵D=[d(ij)]，其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。【分析】

对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，检查d(ij)与d(ik)+d(kj)的值；d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)<这里就是动态规划中的决策>，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了<这就是动态规划中的记忆化搜索>。第十九页，共三十六页，编辑于2023年，星期二7.4.2Floyd算法定义7.4.1:已知矩阵A＝(aij)m×l，B＝(bjk)l×n，规定C＝A*B＝(cij)m×n，其中cij＝min(ai1＋b1j,ai2＋b2j,…,ail＋blj)定义7.4.2已知矩阵A＝(aij)m×n，B＝(bij)m×n，规定D＝AB＝(dij)m×n，其中dij＝min(aij,bij)可以利用上面定义的运算求任意两点间的最短距离。已知n阶加权简单图G，设D＝(dij)m×n

是图G的边权矩阵，即dij＝ω(i,j)(若G是有向图，则dij＝ω<i,j>),若结点i到结点j无边相连时，则取dij＝∞。然后依次计算出矩阵D[2],D[3],…,D[n]及S第二十页，共三十六页，编辑于2023年，星期二7.4.2Floyd算法其中D[2]＝D*D＝()n×nd(2)ij=min{di1+d1j，di2+d2j，…，din＋dnj}d(2)ij表示从vi出发两步可以到达vi的道路中距离最短者。D[3]＝D[2]*D＝()n×n……d(k)ij表示从vi出发k步可以到达vj的道路中距离最短者D[n]＝D[n-1]*D＝()n×nS＝DD[2]D[3]…D[n]＝(Sij)n×n由定义可知dij[k]表示从结点i到j经k边的路（在有向图中即为有向路）中的长度最短者，而Sij为结点i到j的所有路（若是有向图即为有向路）中的长度最短者。Floyd算法的时间复杂性是O(n4)。第二十一页，共三十六页，编辑于2023年，星期二7.4.2Floyd算法求下图各点间的最短路径213465121733621D＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456第二十二页，共三十六页，编辑于2023年，星期二7.4.2Floyd算法解：D(2)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞*＝∞∞2348∞∞∞236∞∞∞∞∞4∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞d14＝min{∞+∞,1+3,2+1,∞+∞,∞+∞,∞+∞,}第二十三页，共三十六页，编辑于2023年，星期二7.4.2Floyd算法类似可得：∞∞∞346∞∞∞∞∞5∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞D(3)＝D(5)＝D(4)＝∞∞∞∞∞6∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞第二十四页，共三十六页，编辑于2023年，星期二7.4.2Floyd算法所以：S＝DD(2)D(3)D(4)D(5)＝(sij)6×6S＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞213465121733621ÅÅÅÅ第二十五页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。

基本思想：通过求解矩阵序列D(0)，D(1)，…，D(n)来实现问题的求解。第二十六页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法其中：D(0)——图的距离矩阵；D(n)——最终解；dij——边(vi,vj)的权值d(k)ij——从vi到vj在所经过的顶点号≤k最短路径长度。即通过依次比较顶点修改路径实现求解的。对于任意两个顶点vi，vj，对于新比较的顶点vk一旦出现d(k-1)ij＞dik＋dkj，则修改对应的d(k)ij。第二十七页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法例：求下图各点间的最短路径213465121733621D＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456第二十八页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法解：比较经过顶点号≤1的矩阵213465121733621D(0)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(1)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456无改变第二十九页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法解：比较经过顶点号≤2的矩阵213465121733621D(1)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(2)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞12345612345648d(1)14＞d12＋d24所以修改d(2)14d(1)16＞d12＋d26所以修改d(2)16第三十页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法解：比较经过顶点号≤3的矩阵213465121733621D(2)＝∞124∞8∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(3)＝∞124∞8∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞1234561234564233d(2)14＞d13＋d34d(2)15＞d13＋d35d(2)24＞d23＋d34d(2)25＞d23＋d35第三十一页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法解：比较经过顶点号≤4的矩阵213465121733621D(3)＝∞12348∞∞1237∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(4)＝∞12248∞∞1237∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456654d(3)16＞d13＋d34＋d46d(3)26＞d23＋d34＋d46d(3)36＞d34＋d46第三十二页，共三十六页，编辑于2023年，星期二7.4.3Floyd-Warshall算法解：比较经过顶点号≤5的矩阵213465121733621D(4)＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(5)＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123