最宽路径的Floyd-Warshall算法

Question

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

设 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。

任何人都可以给我一个伪代码算法，该算法采用 Floyd-Warshall 算法来解决最宽路径问题吗？

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-W算法

您可以更改边的权重，使它们都是唯一的 2 次方，并按原始权重的逆序排列。

也就是说，给出下图（作为加权邻接矩阵）：

0  3  2
16 0  1
5  8  0

我们将其转化为：

0  8  16
1  0  32
4  2  0

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

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

Answer 3

我怀疑Floyd-Warshall算法是否可以适用于解决最宽路径问题。我还没有看到使用 Floyd-Warshall 算法解决最宽路径问题的具体示例。如果有人看到请给我看看。