WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

FindMinimumCostFlow
✖
FindMinimumCostFlow

✖
FindMinimumCostFlow[g,{sd1,sd2,…}]

finds the minimum cost flow in the graph g with sd1, sd2, … vertex supplies or demands.

✖

finds the minimum cost maximum flow between source vertex s and target vertex t in a graph g.

✖

finds the minimum cost flow between source s and target t, with the required flow d.

✖

finds the minimum cost flow in a graph with cost matrix m.

✖
FindMinimumCostFlow[data,…,"property"]

returns the value of "property".

✖
FindMinimumCostFlow[{vw,…},…]

uses rules vw to specify the graph g.

Details and Options

  • FindMinimumCostFlow finds a flow of minimum total cost from a set of supply vertices to a set of demand vertices in a graph with capacity constraints and edge costs.
  • By default, the minimum total cost is returned.
  • Matrices and SparseArray objects can be used in FindMinimumCostFlow.
  • For undirected graphs, edges are taken to have flows in both directions at the same time and same capacities.
  • Self-loops are ignored and parallel edges are merged.
  • FindMinimumCostFlow[data,…,"OptimumFlowData"] returns an OptimumFlowData object flowdata that can be used to extract additional properties, using the form flowdata["property"].
  • FindMinimumCostFlow[data,…,"property"] can be used to directly give the value of "property".
  • Properties related to the optimal flow data include:
  • "CostValue"cost of the flow
    "EdgeList"list of edges contributing to the flow
    "FlowGraph"graph of vertices and edges contributing to the flow
    "FlowMatrix"matrix of edge flows between pairs of vertices
    "FlowValue"value of the flow
    "VertexList"list of vertices contributing to the flow
  • The following options can be given:
  • EdgeCapacityAutomaticcapacity bounds for each edge
    EdgeCostAutomaticcost per unit flow on edges
  • With the default setting EdgeCapacity->Automatic, the edge capacity of an edge is taken to be the EdgeCapacity in the graph g if available, otherwise Infinity.
  • With the default setting EdgeCost->Automatic, the cost per unit flow on an edge is taken to be the EdgeCost in the graph g if available, otherwise 1.
  • FindMinimumCostFlow works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open allclose all

Basic Examples  (2)Summary of the most common use cases

Find the minimum cost flow between supply and demand:

In[2]:=2
✖
https://wolfram.com/xid/0tp74wsks1ok4t-8g1mxg
Out[2]=2

Find the minimum cost maximum flow between two vertices in a graph:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-zswhz4
In[2]:=2
✖
https://wolfram.com/xid/0tp74wsks1ok4t-rrsa87
Out[2]=2

Highlight the flow:

In[3]:=3
✖
https://wolfram.com/xid/0tp74wsks1ok4t-njdf6y
Out[3]=3

Scope  (10)Survey of the scope of standard use cases

FindMinimumCostFlow works with undirected graphs:

In[2]:=2
✖
https://wolfram.com/xid/0tp74wsks1ok4t-gay90t
Out[2]=2

Directed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-1vbgvr
Out[1]=1

Weighted graphs:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-5e2cau
Out[1]=1

Multigraphs:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-s2h57c
Out[1]=1

Mixed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-i4ww80
Out[1]=1

Use rules to specify the graph:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-bndh30
Out[1]=1

Compute the minimum cost flow with vertex supplies:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-sj73o
Out[1]=1

Compute the minimum cost flow with a required flow:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-knszb8
Out[1]=1

Compute the minimum cost flow for a cost matrix:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-cojxn
Out[1]=1

Find properties of a minimum cost flow:

In[1]:=1
✖
https://wolfram.com/xid/0tp74wsks1ok4t-zldbvh

The cost of the flow:

In[2]:=2
✖
https://wolfram.com/xid/0tp74wsks1ok4t-gtx79i
Out[2]=2

List of edges contributing to the flow:

In[3]:=3
✖
https://wolfram.com/xid/0tp74wsks1ok4t-bd3lak
Out[3]=3

Matrix of edge flows:

In[4]:=4
✖
https://wolfram.com/xid/0tp74wsks1ok4t-scruz

Display the flow:

In[5]:=5
✖
https://wolfram.com/xid/0tp74wsks1ok4t-q50o8n
Out[5]=5
Wolfram Research (2012), FindMinimumCostFlow, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html (updated 2015).
✖
Wolfram Research (2012), FindMinimumCostFlow, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html (updated 2015).

Text

Wolfram Research (2012), FindMinimumCostFlow, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html (updated 2015).

✖
Wolfram Research (2012), FindMinimumCostFlow, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html (updated 2015).

CMS

Wolfram Language. 2012. "FindMinimumCostFlow." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html.

✖
Wolfram Language. 2012. "FindMinimumCostFlow." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html.

APA

Wolfram Language. (2012). FindMinimumCostFlow. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html

✖
Wolfram Language. (2012). FindMinimumCostFlow. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html

BibTeX

@misc{reference.wolfram_2025_findminimumcostflow, author="Wolfram Research", title="{FindMinimumCostFlow}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html}", note=[Accessed: 29-March-2025 ]}

✖
@misc{reference.wolfram_2025_findminimumcostflow, author="Wolfram Research", title="{FindMinimumCostFlow}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html}", note=[Accessed: 29-March-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_findminimumcostflow, organization={Wolfram Research}, title={FindMinimumCostFlow}, year={2015}, url={https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html}, note=[Accessed: 29-March-2025 ]}

✖
@online{reference.wolfram_2025_findminimumcostflow, organization={Wolfram Research}, title={FindMinimumCostFlow}, year={2015}, url={https://reference.wolfram.com/language/ref/FindMinimumCostFlow.html}, note=[Accessed: 29-March-2025 ]}