All Pairs Shortest Path (Floyd-Warshall Algorithm)

Find the shortest distance between all pairs of nodes in a weighted directed graph using Floyd-Warshall Algorithm. This dynamic programming approach computes shortest paths between every pair of vertices in a single run, making it efficient for dense graphs or when you need all-pairs shortest paths.

Problem

• Given a weighted directed graph with V vertices and an edge list edges, return a 2D array dist where dist[i][j] represents the shortest distance from node i to node j. If node j is unreachable from node i, dist[i][j] should be Infinity. The distance from a node to itself is always 0.

Note:

• The edge list uses [u, v, weight] format. The algorithm can handle negative edge weights but not negative cycles.

Examples:

Input: V = 4, edges = [[0, 1, 2], [1, 0, 7], [2, 0, 3], [2, 1, 8], [2, 3, 2], [3, 1, 5]]
Output: [
  [0, 2, Infinity, Infinity],
  [7, 0, Infinity, Infinity],
  [3, 5, 0, 2],
  [12, 5, Infinity, 0]
]
Explanation:
- dist[0][1] = 2 (direct edge)
- dist[1][0] = 7 (direct edge)
- dist[2][0] = 3 (direct edge)
- dist[2][1] = 5 (via node 0: 2 -> 0 -> 1, weight: 3 + 2 = 5, shorter than direct 8)
- dist[2][3] = 2 (direct edge)
- dist[3][0] = 12 (via node 1: 3 -> 1 -> 0, weight: 5 + 7 = 12)
- dist[3][1] = 5 (direct edge)

Input: V = 3, edges = [[0, 1, 1], [1, 2, 2], [0, 2, 4]]
Output: [
  [0, 1, 3],
  [Infinity, 0, 2],
  [Infinity, Infinity, 0]
]
Explanation:
- dist[0][2] = 3 (via node 1: 0 -> 1 -> 2, weight: 1 + 2 = 3, shorter than direct 4)

Constraints

• Graph is represented as an edge list where each edge is [u, v, weight]
• Edge weights can be positive, zero, or negative (but no negative cycles)
• V is the number of vertices (nodes numbered from 0 to V-1)
• Graph may contain cycles
• Graph may be disconnected
• Distance from a node to itself is always 0
• Unreachable pairs have distance Infinity
• Algorithm returns a V × V distance matrix

Function Signature

function floydWarshall(V, edges) {
  // Your code here
}

Test Cases

• Base cases: single node V = 1, edges = [] -> [[0]]
• Simple graph: V = 3, edges = [[0, 1, 2], [1, 2, 3]] -> distances via intermediate nodes
• Negative edges: V = 3, edges = [[0, 1, 1], [1, 2, -1], [0, 2, 3]] -> finds shorter path via negative edge
• Disconnected nodes: some pairs will have Infinity distance
• Dense graph: all pairs connected with various weights
• Self-loops: handled correctly (distance to self is 0)