Skip to content

Bellman-Ford ​

bellmanFord(graph, start) devuelve distancias y predecesores y admite pesos negativos. Un ciclo negativo devuelve Err(AlgorithmError) con el código ERR_ALGORITHM_NEGATIVE_CYCLE; propágalo con ? o manéjalo con match.

FirmaDevuelveComplejidad
bellmanFord(adj: [usize, i32][][], start: usize)Result<[i32[], usize?[]], AlgorithmError>tiempo O(VE), memoria O(V)
tyrus
import { AlgorithmError, bellmanFord } from "tyrus:algorithm";

const showPaths = (): Result<void, AlgorithmError> => {
    const graph: [usize, i32][][] = [[[1, 2]], [[2, -1]], []];
    const result = bellmanFord(graph, 0)?;
    print(result[0]); // [0, 2, 1]
    return Ok();
};

match (showPaths()) {
    Ok(_) => {}
    Err(error) => { printError(error.code); // ERR_ALGORITHM_NEGATIVE_CYCLE
    }
}

Resultado de estudio ​

bellmanFordInfo devuelve las métricas de todas las pasadas y relajaciones e informa un ciclo negativo alcanzable como dato, incluida la primera arista que todavía permite relajación.

tyrus
interface BellmanFordInfo {
    distances: i32[];
    predecessors: usize?[];
    relaxationCount: usize;
    processedVertexCount: usize;
    examinedEdgeCount: usize;
    passCount: usize;
    negativeCycleDetected: boolean;
    negativeCycleEdge: [usize, usize, i32]?;
}
tyrus
import { BellmanFordInfo, ShortestPathInfo, bellmanFordInfo } from "tyrus:algorithm";

const info: BellmanFordInfo = bellmanFordInfo([[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []], 0);
print(info.distances); // [0, 3, 1, 4]
print(info.predecessors[3] ?? 99); // 1
print(info.relaxationCount); // 5
print(info.processedVertexCount); // 4
print(info.examinedEdgeCount); // 20
print(info.passCount); // 3
print(info.negativeCycleDetected); // false
const cycleEdge = info.negativeCycleEdge;
print(cycleEdge ? "detected" : "none"); // none