时间戳

首页 > 解决方案 > Floyd-Warshall algorithm for widest path

algorithm - Floyd-Warshall algorithm for widest path

问题描述

I've been looking through graph algorithms for weighted directed graphs, in particular Floyd's algorithm for the All Pairs Shortest Path Problem. Here is my pseudocode implementation.

Let G be a weighted directed graph with nodes {1,...,n} and adjacency matrix A. Let B_k [i, j] be the shortest path from i to j which uses intermediate nodes <= 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

I was wondering if this algorithm (complexity O(n^3)) could be adapted to the widest path algorithm with similar complexity:

Given a weighted, directed graph (G, W), for each pair of nodes i, j find the bandwidth of the path from i to j with greatest bandwidth. If there is no path from i to j, we return 0.

Could anyone give me a pseudocode algorithm adapting the Floyd-Warshall algorithm for the widest path problem?

标签： algorithmgraph-theorydirected-graphfloyd-warshallweighted-graph

解决方案

我假设路径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)。

推荐阅读