Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow problems that I'm aware of include :

  • Cycle cancelling (reff)
  • Successive shortest path
  • Relaxation (reff)
  • Cost scaling (reff)

The above algorithms differ in their approach to solving the problem with some maintaining feasibility and attempting to achieve optimality (Cycle cancelling, Cost scaling) whilst iterating over the flow network and some maintain reduced cost optimality at every step and try to achieve feasibility (Successive Shortest Path, Relaxation).

My question is whether any of the above algorithms or one that I haven't listed, can be altered in order to provide a listing of the k-best flow routings that minimise the overall cost instead of the single optimal routing.


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.