0
$\begingroup$

I am using a directed multigraph to model network flow. For example:

enter image description here Associated with each edge is:

  • a cost of sending flow down that edge (red)
  • a maximum capacity which the amount of flow sent along that edge must not exceed (green)

For each ordered pair of nodes $(i, j)$, I want to find the top-$k$ minimum-cost paths to send flow from $i$ to $j$.

For example, if $k = 4$, then for the journey between $x$ and $y$ I would expect the following table:

Rank  Cost          Capacity
1     0.10  A       2
2     0.20  B       6
3     0.25  C -> D  7    (because max capacity of D is 7)
4     0.35  C -> E  1    (because the path #3 has depleted 7 units of capacity from C)

Note that the capacity column indicates the maximum amount of flow that can be sent along each path, taking into account the reduction in network capacity due to having already sent flow via the higher-ranked paths.

Thus if I wanted to send 5 units of flow from $i$ to $j$, I can read off the above table and know that I should send 2 units along edge $A$ and 3 units along edge $B$.

Is there an existing algorithm for doing this?

Additionally, the cost and capacity associated with each edge may change over time. Ideally, the algorithm should handle updates to edges more efficiently than recomputing the solution for the entire graph again.

$\endgroup$
  • $\begingroup$ Your top $k$ paths might have shared edges, in which case knowing the top $k$ minimum cost paths does not immediately show you the best way to send a large amount of flow from $i$ to $j$, at least if I understand your setup. $\endgroup$ – user2566092 Jul 26 '15 at 16:56
  • $\begingroup$ I see you updated your question statement. Still, at least to me, it's non-trivial to show that the best solution will always take the top paths in a greedy fashion. $\endgroup$ – user2566092 Jul 26 '15 at 17:06

Your Answer

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

Browse other questions tagged or ask your own question.