Floyd-Warshall algorithm for widest path

Question

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?

Answer 1

I assume that bandwidth of a path P is the lowest cost of the edges in P.

If you use b_ij = max(b_ij, min(b_ik, b_kj)) instead of b_ij = min(b_ij, b_ik + b_kj) you can solve the widest path problem. Also, 'no path' initialization set B[i, j] = infinity must change to set B[i, j] = -infinity.

The demonstration its practically the same as in the original problem: induction over the first k vertices as intermediate vertices. The running time isn't modified: ϴ(n^3).