Skip to content

Johnson ​

johnson(graph) calcula rutas más cortas entre todos los pares en grafos ponderados dispersos combinando reponderación con Dijkstra. Un ciclo negativo devuelve Err(AlgorithmError) con el código ERR_ALGORITHM_NEGATIVE_CYCLE; propágalo con ? o manéjalo con match.

FirmaDevuelveComplejidad
johnson(adj: [usize, i32][][])Result<(i32?)[][], AlgorithmError>O(VE + V(V + E) log V)
tyrus
import { AlgorithmError, johnson } from "tyrus:algorithm";

const showDistances = (): Result<void, AlgorithmError> => {
    const distances = johnson([[[1, 4], [2, 2]], [[3, 5]], [[3, 1]], []])?;
    print(distances[0][3] ?? -1); // 3
    return Ok();
};

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

Resultado de estudio ​

johnsonInfo devuelve Result<JohnsonInfo, AlgorithmError> con la matriz de distancias de todos los pares, el conteo de reponderaciones, las relajaciones del Bellman-Ford inicial y las ejecuciones de Dijkstra.

tyrus
interface JohnsonInfo {
    distances: i32?[][];
    reweightingCount: usize;
    bellmanFordRelaxationCount: usize;
    dijkstraExecutionCount: usize;
}
tyrus
import { AlgorithmError, JohnsonInfo, johnsonInfo } from "tyrus:algorithm";

const showStudy = (): Result<void, AlgorithmError> => {
    const info: JohnsonInfo = johnsonInfo([[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []])?;
    print(info.distances[0][3] ?? -1); // 4
    print(info.reweightingCount); // 5
    print(info.bellmanFordRelaxationCount); // 4
    print(info.dijkstraExecutionCount); // 4
    return Ok();
};

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