Finding the maximum bandwidth along a single path in a network

Question

I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths. I have looked at the maximal flow problem and at the Edmond-Karp algorithm. My questions are the following:

1. Edmond-Karp just tells us how much throughput we can get (at the sink) from source to sink if any of the paths were used. Correct?
2. Edmond-Karp does not tell us which path can give us the maximum flow. Correct?

Answer 1

A very simple approach for question 2 is the following. Sort the edges by capacity. Remove the edge with lowest capacity, and check if there is still a path from $s$ to $t$. If there is, move on the edge with the second lowest capacity, and so on.

At some point, we will disconnect $s$ from $t$ by removing an edge of capacity $c$. Now, we know that $c$ is the maximum capacity of a single path from $s$ to $t$.

This algorithm takes time $O(m^2)$, since the connectivity check can be made in time $O(m)$, and we can remove each edge at most once.

Now you can find the actual path (there might be many) of maximum capacity, by finding any $s$-$t$ path in this reduced graph.

When considering node-capacity, remember to change your graph to support that.

Answer 2

Given a path, just iterate along it and find the node with highest capacity.

Distilled from the comments, let us consider this more interesting question:

Given a network of nodes $N$ connected by links $E$ with limited bandwidths $b : E \to \mathbb{N}$, find a path from $s$ to $t$ with maximum bandwith.

In other words, you are looking for an $s$-$t$-path $p = (s, v_1, \dots, v_k, t)$ that maximises

$\qquad \displaystyle B(p) := \min\ \{ b(s,v_1), b(v_k, t) \} \cup \{b(v_i,v_{i+1} \mid i = 1, \dots, k-1\} $

among all $s$-$t$-paths.

It is noteworthy that cycles do not change path bandwith $B$, so we can restrict ourselves to minimal paths in this respect, that is look at $B$-optimal spanning trees.

Note furthermore that among all $B$-optimal paths, there is (at least) one that has the subpath-optimality property we know from the shortest path problem, that is that all partial paths of an optimal paths are optimal (for the nodes they connect). It does not hold for all $B$-optimal paths¹, but that is not a problem: what we need to know is that there is a $B$-optimal path that can be constructed from a concatenation of $B$-optimal paths. Therefore, we can restrict ourselves to considering only such (partial) paths.

With this we have collected enough justification for a greedy strategy similar to Prim's algorithm: starting in $s$, successively choose edges with maximum bandwith among those edges incident to already visited nodes (that do not connect two already visited nodes). This will discover only $B$-optimal paths and therewith a $B$-optimal $s$-$t$-path (if $t$ is reachable from $s$).

This runs in time $O(|N|^2)$.

---

1. Consider this graph:

   
   ^[source]

   All $s$-$t$-paths are optimal, but those that go via the lower node have non-optimal subpaths.

Answer 3

This can be done in O(VlogV + E) time by doing a simple modification to Dijkstra

key(Node n) = single path max flow from s to n

Update Key: if p is the predecessor of n Key(n) = min(Key(p), edge(p, n))

This is because for all paths P=(s, a_2, ... a_m-1, a_m)

Max flow in path P= min( capacity(a_m-1, a_m), Max flow in P-{a_m} )

This works because single path max flow to x = max( Max flow in path all paths P from s to x )