东直门小学的网站建设,阿里云个人网站备案做淘客,数字营销案例100例,企业注册百家号可以做网站吗本章考虑在给定的有向加权图G(V, E)#xff0c;对于所有的节点u,v∈V#xff0c;找到一条从节点u到节点v的最短路径。希望以表格的形式表示输出#xff1a;第u行第v列给出的是节点u到节点v的最短路径权重。 对于这个问题#xff0c;如果是运行|V|次单源最短路径算法来解决所… 本章考虑在给定的有向加权图G(V, E)对于所有的节点u,v∈V找到一条从节点u到节点v的最短路径。希望以表格的形式表示输出第u行第v列给出的是节点u到节点v的最短路径权重。 对于这个问题如果是运行|V|次单源最短路径算法来解决所有节点对的最短路径问题每一次使用一个不同的节点做为源节点。如果所有边的权值是非负的可以采用Dijkstra算法。如果采用数组来实现最小优先队列算法的运行时间为O()O()。使用二叉堆实现的最小优先队列将使算法的运行时间降低到O(VE lg V)这个时间在稀疏图的情况下有很大改进因为稀疏图E 。如果采用斐波那契堆来实现最小优先队列其算法运行时间为O()。 如果图中有权重为负值的边就必须采用效率更低的Bellman-Ford算法这样的运行时间将使O()在稠密图的情况下该运行时间为O()。 本章研究的算法将能做到更好同时本章还讨论所有节点对最短路径问题与矩阵乘法之间的关系。 本章的多数算法采用邻接矩阵表示图假定节点的编号为1,2,...,|V|因此算法的输入是n*n的矩阵W该矩阵代表一个有n个节点的有向图的边的权重 算法的输出也是一个n*n的矩阵D ()。其中 δ(i, j)。 为了解决所有顶点间最短路径问题不仅要算出最短路径的权值而且要计算出一个前驱节点矩阵其中在ij或从i到j没有通路时为NIL其他情况下表示从i到j的某条最短路径上j的前驱顶点。由矩阵的第i行导出的子图应是根节点为i的一棵最短路径树。下面的算法将打印出从节点i到节点j的一条最短路径该算法类似于22章的PRINT-PATH过程 PRINT-ALL-PAIRS-SHORTEST-PATH(, i, j) if i j print i else if NIL print “no path from i to j exists” else PRINT-ALL-PAIRS-SHORTEST-PATH(, i, ) print j 本章使用大写字母表示矩阵如W, L或D使用带下标的小写字母表示矩阵中的个体元素如、或。 一最短路径和矩阵乘法 本节讨论一种动态规划算法动态规划算法的步骤是分析最优解的结构递归定义最优解的值自底向上计算最优解的值。 之前讨论单源最短路径问题时已经证明一条最短路径的所有子路径都是最短路径。考虑从i到j的一条最短路径p假定p最多包含m条边假定没有权值为负值的环路且m为有限值。如果ij则p的权重为0且不包含任何边。如果i和j不同则将p分解为其中路径p’最多包含m-1条边所以δ(i, j) δ(i, k)。 设为从i到j的最多包含m条边的任意路径中的最小权重。当m0时从i到j之间存在一条没有边的最短路径当且仅当ij。所以 对于m0有 。 如果i到j之间最短路径则该路径为简单路径其中包含的边最多为n-1所以有 对于所有的节点i和j有 ()所以 W。下面的算法假定已经知道了W和的情况下给出如何计算其中L表示 L’表示该算法的时间复杂度为O() 现在可以看到上面的算法与矩阵乘法的关系了。假定希望计算矩阵乘积C A*B对于ij1,2...,n有 。如果在 做出下面的替换 就可以得到 。因此如果对算法EXTEND-SHORTEST-PATHS做出上面的替换就可以得到标准的矩阵乘法的算法。 如前所述矩阵包含的是最短路径权重所以下面的算法可以在O()时间内计算出该矩阵阵列 我们的目标并不是要计算所有的矩阵我们感兴趣的仅仅是矩阵。因为有正如传统的矩阵乘法是相关的所以由EXTEND-SHORTEST-PATHS过程所定义的算法也是相关的。所以可以采用重复平方的技术计算该矩阵序列该算法的时间复杂度可以减少为O() 二Floyd-Warshall算法 Floyd-Warshall算法采用不同的动态规划公式解决所有节点对的最短路径问题它的运行时间是O()该算法同样假设可以存在负权重的边但不能存在权重为负值的环路。 Floyd-Warshall算法考虑一条最短路径上的中间节点这里简单路径p上的中间节点指的是路径p上除和之外的任意结点。 假定图G的所有节点V{12...,n}考虑其中的子集{12...,k}。对于任意的结点ij∈V考虑从i到j的所有中间节点均取自集合{12...,k}的路径。并设p为其中的最短路径分两种情况讨论 a如果结点k不是p上的中间节点则路径p上的所有中间节点都属于集合{12...,k-1}。因此从i到j的中间节点均取自集合{12...,k}的一条最短路径同样也是从i到j的中间节点均取自集合{12...,k-1}的一条最短路径。 b如果结点k是路径p上的中间节点则p可以分解为所以p1上的所有中间节点都属于集合{12...,k-1}同理p2也是。 根据上面的观察设为从i到j的所有中间节点全部取自集合{12...,k}的一条最短路径的权重。当k0时i到j的路径没有中间节点这样的路径最多只有一条边所以有 。根据上面的讨论可以有 因为对于所有的路径所有的中间节点都属于集合{1,2,...,n}矩阵给出的就是最终的矩阵 δ(i, j)。算法如下该算法的运行时间为O() 另外可以在计算的同时计算前驱矩阵具体来说需要计算一个矩阵序列这里 并且定义 为从i到j的一条所有中间节点都取自集合{1,2,...,k}的最短路径上j的前驱结点。 所以可以给出的一个递归公式当k0时从i到j的一条最短路径上没有中间节点所以 如果k1则有 这样就可以在计算的同时计算前驱矩阵了下面是一个运算过程 给定有向图G(V, E)结点集合V{12..., n}希望判断对于所有的i和j图G中是否包含一条从节点i到j的路径这称为图G的传递闭包问题。 一种计算图G的传递闭包的办法是给E中的每条边赋予权重1然后运行Floyd-Warshall算法如果存在一条从i到j的路径则有 n否则。这种算法的时间复杂度为O()。 可以有另外一种算法该算法使用逻辑或操作和逻辑与操作替换Floyd-Warshall算法中的算术操作min和。对于i,j,k1,2,...,n定义如果图G中存在一条从节点i到结点j的所有中间节点都取自集合{1,2,...,k}的路径则 1否则 0。所以当k0时有 对于k1有: 所以算法如下 该算法从结构上类似于Floyd-Warshall算法运行时间为O()但是逻辑运算通常要比算术运算要快而且TRANSITIVE-CLOSURE所需要的空间更少。 三用于稀疏图的johnson算法 johnson算法可以在O()时间内找到所有节点对之间的最短路径。对于稀疏图来说算法在渐近意义上要好于矩阵的重复平方法或Floyd-Warshall算法。算法要么返回一个包含所有节点对的最短路径权重的矩阵要么报告输人图中存在一个负权值的回路。算法需要使用Dijkstra算法和Bellman-Ford算法作为其子程序。 Johnson算法使用的技术称为重新赋予权重。如果图G(V, E)中所有的边权重w皆为非负值则可以采用对每个节点运行Dijkstra算法找到所有节点对的最短路径如果该图包含权重为负值的边但没有权重为负值的环路则只要计算出一组新的非负权重值然后使用同样的方法即可。新赋予的权重w’必须满足下面的性质 a多于所有顶点对u、v∈V一条路径p是利用加权函数w时从u到v的一条最短路径当且仅当p也是利用加权函数w’时从u到v的一条最短路径。 b对于所有的边(u, v)新的权重w’(u, v)是非负值。 给定带权重的有向图G(V, E)其权重函数为w设h: v-R为任意函数该函数将节点映射到实数上。对于每条边(u,v)定义w’(u,v) w(u, v) h(u) – h(v)。设p 为从节点到节点的任意一条路径那么p是在使用权重函数w时从节点到节点的一条最短路径当且仅当p是在使用权重函数w’时从节点到节点的一条最短路径。即w(p) δ()当且仅当w’(p) δ()。而且图G在使用权重函数w时不包含负值环路当且仅当G在使用权重函数w’时不包含负值环路。 下一个目标是确保第二个属性成立也就是所有边(u, v)w’(u,v)0。如果给定图G(V, E)制作一幅新图G’ (V’, E’)。其中V’ V∪{s}s是一个新节点。E’ E∪ {(s,v): v∈V}并且对于所有节点v∈V, w(s, v) 0。所以G’不包含权重为负值的环路当且仅当图G不包含权重为负值的环路。现在定义函数h对于所有节点v∈V’h(v) (s)。所以w’(u, v) w(u, v) h(u) – h(v)。根据三角不等式定理可以得到w’(u, v)0。 Johnson算法执行过程中需要使用Bellman-ford算法和Dijkstra算法。该算法假定所有的边都保存在邻接链表里返回一个|V|*|V|的矩阵D 其中 δ(i, j)。 如果使用斐波那契堆来实现Dijkstra算法则Johnson算法的运行时间为O(),使用更简单的二叉堆实现则时间为O(VE lg V)在稀疏图的情况下仍然比Floyd-warshall算法快。 转载于:https://www.cnblogs.com/gqtcgq/p/7247220.html
