Skip to contents

Finds the minimum cost flow of a directed graph.

Usage

MinCostFlow(
  arcSources,
  arcTargets,
  arcCapacities,
  arcCosts,
  nodeSupplies,
  numNodes,
  algorithm = "NetworkSimplex"
)

Arguments

arcSources

Vector corresponding to the source nodes of a graph's edges

arcTargets

Vector corresponding to the destination nodes of a graph's edges

arcCapacities

Vector corresponding to the capacities of nodes of a graph's edges

arcCosts

Vector corresponding to the capacities of nodes of a graph's edges

nodeSupplies

Vector corresponding to the supplies of each node

numNodes

The number of nodes in the graph

algorithm

Choices of algorithm include "NetworkSimplex", "CostScaling", "CapacityScaling", and "CycleCancelling". NetworkSimplex is the default.

Value

A named list containing four entries: 1) "flows": A vector corresponding to the flows of arcs in the graph, 2) "potentials": A vector of potentials of the graph's nodes, 3) "cost": the total cost of the flows in the graph, i.e. the mincostflow value, and 4) "feasibility": LEMON's feasibility type, demonstrating how feasible the graph problem is, one of "INFEASIBLE", "OPTIMAL", and "UNBOUNDED"

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00612.html.