29. Floyd-Warshall

Hard

Topics

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

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

Output: [[0, 3, 5, 8], [Infinity, 0, 2, 5], [Infinity, Infinity, 0, 1], [Infinity, Infinity, Infinity, 0]]

Explanation: The shortest path from vertex 0 to vertex 1 is 3. The shortest path from vertex 0 to vertex 2 is 3 + 2 = 5 (through vertex 1). The shortest path from vertex 0 to vertex 3 is 3 + 2 + 1 = 6 (through vertex 1 and 2). Updated: The shortest path from vertex 0 to vertex 3 is actually 3 + 5 = 8 (0 -> 1 -> 3). The initial matrix after processing edges is [[0, 3, 8, Infinity], [Infinity, 0, 2, 5], [Infinity, Infinity, 0, 1], [Infinity, Infinity, Infinity, 0]]. After iterations, it calculates the shortest distance between each pair. Note that nodes unreachable from the source stay as Infinity.

Example 2:

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

Output: [[-1, 4, 1], [-1, 2, -3], [-1, 4, 1]]

Explanation: This graph contains negative weights. The algorithm correctly calculates the shortest path, including the impact of negative weights.

Constraints:

Time Complexity

O(V³)

Space Complexity

O(V²)