Please read the new rule regarding the restriction on the use of AI tools. ×

Haruka's blog

Maximum weighted network flow with lower and upper bounds
By Haruka, history, 10 months ago, In English

Recently I have read about the Edmonds-Karp algorithm and the solution to the flows with demands problem. Thus, I come up with the following problem but haven't found a solution yet:

Given a directed graph G(V, E) including a source s (no incoming edge) and a sink t (no outgoing edge). Each edge e in E consists of 3 attributes: l(e), u(e), w(e). Find a flow f from s to t such that l(e) <= f(e) <= u(e) for all edges e in E and the sum of w(e)f(e) is maximized?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

You can just google the title of your blog and the first result should be the one you need.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking at the stuff you already covered, i think you should be able to modify the "flow with demands" in such a way that it solves "mincost flow with demands"

→ Reply