Skip to content

Floyd-Warshall ​

floydWarshall(graph) computes shortest distances between every pair. The input may be an (i32?)[][] weight matrix or Graph<N, i32>; absent entries represent missing edges.

SignatureReturnsComplexity
floydWarshall(matrix: (i32?)[][])(i32?)[][]O(V³) time, O(V²) memory
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

Study result ​

floydWarshallInfo returns the final matrix, the number of intermediate-vertex passes and distance updates, and whether the final diagonal reveals a negative cycle.

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