最宽路径的Floyd算法

Question

我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。

设G是一个具有节点{1，…，n}和邻接矩阵A的加权有向图。设B_k i，j是从i到j的最短路径，它使用中间节点<= k。

input A

if i = j then set B[i, j] = 0
  set B[i, j] = 0
else if i != j && there is an arc(i, j)
  set B[i, j] = A[i, j]
else 
  set B[i, j] = infinity

#B = B0
for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      b_ij = min(b_ij, b_ik + b_kj)
return B

我想知道这个算法(复杂度O(n^3))是否可以适应具有类似复杂度的最宽路径算法：

给定一个加权有向图(G，W)，对每对节点i，j求出带宽最大的从i到j的路径带宽。如果没有从i到j的路径，则返回0。

有人能给我一个伪码算法，以适应最宽的路径问题的弗洛伊德-沃尔算法吗？

Answer 1

我假设路径P的带宽是P中边沿的最低成本。

如果使用b_ij = max(b_ij, min(b_ik, b_kj))而不是b_ij = min(b_ij, b_ik + b_kj)，则可以解决最宽的路径问题。此外，“无路径”初始化set B[i, j] = infinity必须更改为set B[i, j] = -infinity。

该演示实际上与原问题相同:在第一个k个顶点上的归纳作为中间顶点。运行时间没有被修改:ϴ(n^3)。

Answer 2

您可以通过增强图来使用F算法。

你可以改变边的权值，使它们都是唯一的二次幂，与原始权值的倒数排序。

也就是说，给定以下图(作为加权邻接矩阵)：

0  3  2
16 0  1
5  8  0

我们将其转化为：

0  8  16
1  0  32
4  2  0

我们现在可以简单地找到这个新图上的最短路径，这将是原始图上最宽的路径。

要看到这一点，请注意，任何2的幂都大于2的所有较低的幂，因此最短路径将优先最小化最大的权重，因为这也最小化了总重量。这相当于避免最初问题中最狭窄的路径，这正是我们所想要的。