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.
| Firma | Devuelve | Complejidad |
|---|---|---|
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); // 2Resultado 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