Skip to content

SPFA ​

spfa(graph, start) calcula rutas más cortas desde un origen con pesos negativos y devuelve distancias y predecesores. Un ciclo negativo devuelve Err(AlgorithmError) con el código ERR_ALGORITHM_NEGATIVE_CYCLE; propágalo con ? o manéjalo con match.

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

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

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

Resultado de estudio ​

spfaInfo devuelve Result<SpfaInfo, AlgorithmError> y agrega inserciones y extracciones de la cola, tamaño máximo de la cola y las métricas compartidas de camino mínimo. Un ciclo negativo alcanzable se devuelve como Err(AlgorithmError).

tyrus
interface SpfaInfo {
    distances: i32[];
    predecessors: usize?[];
    relaxationCount: usize;
    processedVertexCount: usize;
    examinedEdgeCount: usize;
    queuePushCount: usize;
    queuePopCount: usize;
    maxQueueSize: usize;
}
tyrus
import { AlgorithmError, SpfaInfo, spfaInfo } from "tyrus:algorithm";

const showStudy = (): Result<void, AlgorithmError> => {
    const info: SpfaInfo = spfaInfo([[[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); // 6
    print(info.queuePushCount); // 6
    print(info.queuePopCount); // 6
    print(info.maxQueueSize); // 2
    return Ok();
};

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