5
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ also, is there any algo which can tell me that path x-a-c will give me a maximum throughput from x to c? $\endgroup$ – Amaar Bokhari Apr 30 '12 at 14:20
  • 4
    $\begingroup$ The maximum flow is NOT a SINGLE path! $\endgroup$ – uli Apr 30 '12 at 14:35
  • $\begingroup$ @AmaarBokhari Please see my edits to make sure I have preserved your meaning. Also, see uli's comment regarding the maximum flow in a network. What you might be looking for is actually this: en.wikipedia.org/wiki/Longest_path_problem If that looks right, feel free to provide an answer yourself based on the article, or at least let us know so we can address more specific questions arising therefrom. If the linked problem is not the one in which you're interested... sorry for my confusion! $\endgroup$ – Patrick87 Apr 30 '12 at 16:21
  • $\begingroup$ @Patrick87....i would agree with Uli's comments.His comments somehow confirmed my doubts as I was,too, thinking that maximum flow just gives us the answer that how much throughput can be observed at the sink (using maximum flow's terminology). I am familiar with the longest path problem but that is not my question. :) But thanks to you both! $\endgroup$ – Amaar Bokhari Apr 30 '12 at 20:37
  • 1
    $\begingroup$ @AmaarBokhari This sounds to me more like a static routing problem than a maximum flow problem in the Edmonds-Karp sense. If you are not looking for a maximum flow but only for a single max capacity path I would check if a modified version of Dijkstra’s algorithm can do the job. $\endgroup$ – uli May 2 '12 at 20:22
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

    example
    [source]

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

$\endgroup$
0
$\begingroup$

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 )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.