Skip to content

Floyd-Warshall ​

floydWarshall(graph) calcula las distancias más cortas entre todos los pares. La entrada puede ser una matriz de pesos (i32?)[][] o Graph<N, i32>; las ausencias representan aristas inexistentes.

FirmaDevuelveComplejidad
floydWarshall(matrix: (i32?)[][])(i32?)[][]tiempo O(V³), memoria O(V²)
tyrus
import { floydWarshall } from "tyrus:algorithm";

const matrix: (i32?)[][] = [[0, 4, 2], [0, 0, 0], [0, 0, 0]];
const distances = floydWarshall(matrix);
print(distances[0][2] ?? -1); // 2

Resultado de estudio ​

floydWarshallInfo devuelve la matriz final, el número de pasadas por vértice intermedio y actualizaciones de distancia y si la diagonal final revela un ciclo negativo.

tyrus
interface FloydWarshallInfo {
    distances: i32?[][];
    kPassCount: usize;
    distanceUpdateCount: usize;
    negativeCycleDetected: boolean;
}
tyrus
import { FloydWarshallInfo, Graph, floydWarshallInfo } from "tyrus:algorithm";

const graph = Graph<i32, i32>();
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 1);
graph.addEdge(1, 3, 1);
graph.addEdge(2, 1, 2);
graph.addEdge(2, 3, 5);
const info: FloydWarshallInfo = floydWarshallInfo(graph);
print(info.distances[0][3] ?? -1); // 4
print(info.kPassCount); // 4
print(info.distanceUpdateCount); // 4
print(info.negativeCycleDetected); // false