Skip to content

edmondsKarp ​

edmondsKarp(capacity, source, sink) calcula o fluxo máximo em uma matriz de capacidades e retorna o valor e as arestas de fluxo positivas.

AssinaturaRetornoComplexidade
edmondsKarp(capacity: i32[][], source: usize, sink: usize)[i32, [usize, usize, i32][]]O(VE²)
tyrus
import { edmondsKarp } from "tyrus:algorithm";

const result: [i32, [usize, usize, i32][]] = edmondsKarp([[0, 2], [0, 0]], 0, 1);
print(result[0]); // 2

Resultado de estudo ​

tyrus
interface EdmondsKarpInfo { maxFlow: i32; augmentationCount: usize; examinedEdgeCount: usize; flowEdges: [usize, usize, i32][]; bfsRunCount: usize; augmentingPathLengths: usize[]; maxFrontierSize: usize; }
tyrus
import { EdmondsKarpInfo, FlowInfo, edmondsKarpInfo } from "tyrus:algorithm";
const info: EdmondsKarpInfo = edmondsKarpInfo([[0, 3, 2, 0], [0, 0, 1, 2], [0, 0, 0, 3], [0, 0, 0, 0]], 0, 3);
print(info.maxFlow); // 5
print(info.flowEdges); // [[0, 1, 3], [0, 2, 2], [1, 2, 1], [1, 3, 2], [2, 3, 3]]
print(info.augmentationCount); // 5
print(info.examinedEdgeCount); // 16
print(info.bfsRunCount); // 6
print(info.augmentingPathLengths); // [5]
print(info.maxFrontierSize); // 4