Floyd–Warshall Algorithm

Given a square adjacency matrix of a directed graph, return a matrix containing the shortest distance for every ordered pair of vertices. Row start and column…

Given a square adjacency matrix of a directed graph, return a matrix containing the shortest distance for every ordered pair of vertices. Row start and column end describe the directed route from start to end: matrix[start][end] is its direct edge weight, and result[start][end] is its shortest distance. A value of -1 means no direct edge; every other value is a nonnegative edge weight. Return -1 for an unreachable pair. Each vertex has distance zero to itself through the empty path, even when its input diagonal is -1 or positive. Do not modify the caller's matrix.

1 ≤ number of vertices ≤ 100. The matrix is square. Every cell is an integer from -1 through 1000; -1 is the absent-edge sentinel, not a negative edge. The visualizer accepts at most 6 vertices to keep the cubic teaching timeline bounded. Run and Submit retain the full 100-vertex domain.

Example 1: input matrix = [[0, 2, -1], [-1, 0, 3], [-1, -1, 0]]; output [[0, 2, 5], [-1, 0, 3], [-1, -1, 0]]. The route from vertex 0 through vertex 1 to vertex 2 costs 2 + 3 = 5. No reverse routes are introduced.

Example 2: input matrix = [[7]]; output [[0]]. The empty self path has cost zero and is shorter than the positive self edge.

Category: Graphs. Topic: graph. Difficulty: Hard. Patterns: graph-traversal.