---
title: "Maximum Flow, Minimum Cut, and Shortest Paths"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/flow.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/flow.md"
part: "Combinatorics"
chapter: "Graphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Distances, Paths, and Circuits in a Graph", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/path-circuit-graph.md"}
next: {"title": "Matrices and Vector Spaces Associated with a Graph or Digraph", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/matrix-vector-space.md"}
---

<a id="flow"></a>
<a id="graph-sec-flow"></a>
# Maximum Flow, Minimum Cut, and Shortest Paths

Whenever the edges of a graph are assigned a capacity it is possible to compute the maximum flow and the minimum cut of the graph. Whenever the edges of a graph are assigned a weight it is possible to find shortest paths in the graph. If one wants to perform these computations on a graph where none of its edges have been assigned a capacity or a weight, then the edges are taken to have a capacity or weight of one, and the computations are carried out accordingly.

The flow-based and shortest-paths algorithms and the resulting functionalities are fully documented in Chapter [Multigraphs](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/index-multigraphs.md#multigraph), Sections [Maximum Flow and Minimum Cut](https://docs.magma-maths.org/v2.30-1/Combinatorics/Networks/flow.md#multigraph-sec-flow) and [Distances, Shortest Paths, and Minimum Weight Trees](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/shortest-paths.md#multigraph-sec-shortp) respectively.
