{
  "id": "enwiki-001332013179",
  "slug": "circulation-problem",
  "title": "Circulation problem",
  "qid": "",
  "lead": "The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special nodes). In variants of the problem, there are multiple commodities flowing through the network, and a cost on the flow.",
  "body": "The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special nodes). In variants of the problem, there are multiple commodities flowing through the network, and a cost on the flow. \\sum_{w \\in V} f(u,w) = 0 (flow cannot appear or disappear in nodes). Finding a flow assignment satisfying the constraints gives a solution to the given circulation problem. In the minimum cost variant of the problem, minimize \\sum_{(v,w) \\in E} c(v,w) \\cdot f(v,w). \\ \\sum_{w \\in V} f_i(u,w) = 0. Multi-commodity flow - If K_i(s_i,t_i,d_i) denotes a demand of d_i for commodity i from s_i to t_i , create an edge (t_i,s_i) with l_i(t_i,s_i) = u(t_i,s_i) = d_i for all commodities i . Let l_i(u,v)=0 for all other edges. Minimum cost multi-commodity flow problem - As above, but minimize the cost. Minimum cost flow problem - As above, with 1 commodity. Maximum flow problem - Set all costs to 0, and add an edge from the sink t to the source s with l(t,s)=0 , u(t,s)= ∞ and c(t,s)=-1 . Minimum cost maximum flow problem - First find the maximum flow amount m . Then solve with l(t,s)=u(t,s)=m and c(t,s)=0 . Single-source shortest path - Let l(u,v)=0 and c(u,v)=1 for all edges in the graph, and add an edge (t,s) with l(t,s)=u(t,s)=1 and c(t,s)=0 . All-pairs shortest path - Let all capacities be unlimited, and find a flow of 1 for v(v-1)/2 commodities, one for each pair of nodes.",
  "categories": [
    "125876068",
    "20477143",
    "23603337",
    "26220375",
    "29176510"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1332013179",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1767956464.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001332013179",
    "type": "webpage",
    "title": "Circulation problem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/circulation-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001332013179",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1332013179",
    "note": "Immutable snapshot enwiki-001332013179"
  }
}