I am using a directed multigraph to model network flow. For example:
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.