Finding the maximum bandwidth along a single path in a network

Problem Detail: 

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?

Asked By : Amaar Bokhari

Answered By : utdiscant

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1591