Floyd-Warshall Algorithm

Given a weighted directed graph with **n** vertices (edge weights may be negative, but no negative cycles), compute the **shortest distance between every pair of vertices** using the **Floyd-Warshall algorithm**. Return the result as an n×n matrix, where unreachable pairs have distance `Infinity`.

Examples

Input: n = 3, edges = [[0,1,3],[1,2,1],[0,2,10]]

Output: matrix[0][2] = 4

The path 0→1→2 (3+1=4) is shorter than the direct edge 0→2 (10).

Constraints

• 1 <= n <= 300
• No negative cycles
• edges[i] = [u, v, weight]

Complexity Analysis

Time

O(V^3)

three nested loops over all vertices.

Space

O(V^2) for the distance matrix.

Test Cases

#1 — Shorter path found through intermediate node

Input: n=3 edges=[[0,1,3],[1,2,1],[0,2,10]]

Expected: matrix[0][2] === 4

#2 — No return edge — unreachable

Input: n=2 edges=[[0,1,5]]

Expected: matrix[1][0] === Infinity

#3 — Single vertex, distance to self is 0

Input: n=1 edges=[]

Expected: matrix[0][0] === 0

Step-by-step visualizer available!

Switch to the Visualize ✨ tab to watch this algorithm run step-by-step on a live graph before you code.