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.
| Assinatura | Retorno | Complexidade |
|---|---|---|
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]); // 2Resultado 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