太平保险网站,腾讯云可以用wordpress教程,常州第一门户网,南宁网站开发招聘问题描述 给定一个带权重的有向图G(V,E)#xff0c;其权重函数为ω:E→R。 在图中#xff0c;对所有的结点对 u,v∈V#xff0c;找出从结点u到结点v的最短路径。 该问题的解以表格#xff08;二维数组#xff09;的形式给出#xff1a;第u行第v列给出从结点u到结…问题描述 给定一个带权重的有向图G(V,E)其权重函数为ω:E→R。 在图中对所有的结点对 u,v∈V找出从结点u到结点v的最短路径。 该问题的解以表格二维数组的形式给出第u行第v列给出从结点u到结点v的最短路径权重。
约定 1结点编号不失一般性结点编号为12…|V|。 2成本邻接矩阵图G用一个n╳n的邻接矩阵W(wij)表示 其中 3允许存在权重为负值的边但不能包含权重为负值的环路否则无解。 4最短路径矩阵算法的输出为一个n╳n的最短路径矩阵 D(dij)其中dij表示从结点i到结点j的一条 最短路径的权重。算法结束时有dijδ(i,j)。 5前驱结点矩阵 前驱结点矩阵记为П(πij)其中 利用前驱结点矩阵П可以计算出每对结点间的最短路径。 前驱结点矩阵П的第i行所诱导的子图是一棵根结点为i的最短路径树。 对于每个结点i∈V定义图G对于结点i的前驱子图为 Gπ,i(Vπ,i,Eπ,i)其中 见CHP24 打印最短路的过程 动态规划做法
最短路径的最优子结构性质 每条路径都是最短路径考虑从结点i到结点j的一条最短路径p。假定p至多包含m条边假定没有权重为负值的环路且m为有限值。 如果ij则p中不包含任何边所以p的权重等于0 如果i ≠ j则将路径p分解为 其中 p ’至多包含 m-1 条边则p ’是从i到k的一条最短路径 且δ(i,j)δ(i,k)Wkj。
递归解 设是从结点i到结点j的至多包含m条边的任意路径中的最小权重。 则
自底向上解
(伪代码在给定W和L(m-1)的情况下计算L(m)) 时间复杂度
发现这个计算过程实际上很类似于矩阵乘法几乎完全一样可以用矩阵快速幂优化到。
另一种DP——Floyd-Warshall算法 算法允许图中存在负权重的边但不能存在权重为负值的环路。
思路 假定图G的结点集为V{1,2,…,n}。考虑其中的一个子集 {1,2,…,k}这里k是小于n的某个整数并是其中的最大编号。 对于任意一对结点i,j∈V定义p是从i到j、且所有中间结点均取自于集合{1,2,…,k}的最短路径。 p是简单路径且p的中间结点都不大于k。 p从i 到 j仅经过集合{1,2,…,k}中的结点但 不一定经过其中的每一个结点 也可能不存在这样的路径此时p的权重等于∞。
在从 i 到 j 之间中间结点均取自集合{1,2,…,k-1}的基础上试图回答这样一个问题结点k是否是路径p上的一个中间结点 1如果结点k不是路径p上的中间结点则p上的所有中间结点都属于集合{1,2,…,k-1}。 此时从结点i到结点j的中间结点取自集合{1,2,…,k-1}的一条最短路径也是从结点i到结点j的中间结点取自集合 {1,2,…,k}的一条最短路径。 2如果结点k是路径p上的中间结点则k将路径p分解为两段如下图最优子结构性p1是从结点i到结点k的一条最短路径且中间结点全部取自集合{1,2,…,k-1} 。 因为结点k不是路径p1上的中间结点所以路径p1上的所有结点都 属于集合{1,2,…,k-1} 。 同理p2是从结点k到结点j的一条最短路径且中间结点全部取自集合{1,2,…,k-1} 故有状态转移方程 伪代码 时间复杂度
加入最短路径构建 为从结点i到结点j的一条所有中间结点都取自集合 {1,2, …, k}的最短路径上j的前驱结点。 应用——计算传递闭包 定有向图G(V,E)定义图G的传递闭包G*(V,E*)其中 E*{(i,j)如果图G中包含一条从结点i到结点j的路径}。 求有向图的传递闭包 方法一给E中每条边赋权重1然后运行FLOYD-WARSHALL算法 可以在Θ(n3)求出权重路径矩阵D。在D中若dijn则表示存在一条从结点i到结点j的路径否则dij∞。 方法二定义矩阵T {tij}若存在一条从结点i到结点j的路径tij1否则tij0。 计算T 对FLOYD-WARSHALL算法进行改造用逻辑或操作V和 逻辑与操作Λ替换算术操作min和得以下计算公式 用于稀疏图的Johnson算法 Johnson算法在稀疏图中求每对结点之间的最短路径权重。 对稀疏图Johnson算法优于Floyd-Warshall算法时间复杂度可达O(V2lgVVE)。 Johnson算法使用Dijkstra算法和Bellman-Ford算法作为自己的子程序可处理带有负权重的图。 如果图中包含所有结点对的最短路径Johnson算法输出一个包含所有结点对的最短路径权重矩阵否则报告图中包含权重为负值的环路。 重赋权重Johnson算法使用重新赋予权重的技术求解。
