Floyd Warshall All Pairs Shortest Path in DSA Javascript

Mental Model

We find the shortest paths between every pair of points by checking if going through a middle point is better than going directly.

Analogy: Imagine you want to travel between cities. Sometimes going through a third city is faster than going straight. We check all cities as possible middle stops to find the quickest routes.

  [A]---5---[B]
   |         |
  10        3
   |         |
  [C]-------[D]
       1

Distances:
A->B=5, A->C=10, B->D=3, C->D=1
We want shortest paths between all pairs.

Dry Run Walkthrough

Input: Graph with nodes A, B, C, D and edges: A->B=5, A->C=10, B->D=3, C->D=1

Goal: Find shortest distances between every pair of nodes using Floyd Warshall

Step 1: Initialize distance matrix with direct edges and 0 for same nodes

dist = {
  A: {A:0, B:5, C:10, D:∞},
  B: {A:∞, B:0, C:∞, D:3},
  C: {A:∞, B:∞, C:0, D:1},
  D: {A:∞, B:∞, C:∞, D:0}
}

Why: We start with known direct distances and zero for same nodes

Step 2: Use A as intermediate node to update distances

No shorter paths found using A as middle, dist unchanged

Why: No paths improve by going through A since A only connects to B and C directly

Step 3: Use B as intermediate node to update distances

dist[A][D] updated from ∞ to 8 (A->B=5 + B->D=3)
Others unchanged

Why: Going A->B->D is shorter than no direct path A->D

Step 4: Use C as intermediate node to update distances

dist[A][D] updated from 8 to 11 (A->C=10 + C->D=1) but 8 is shorter, so keep 8
No change

Why: Check if going through C improves paths; it does not improve A->D here

Step 5: Use D as intermediate node to update distances

No shorter paths found using D as middle, dist unchanged

Why: D has no outgoing edges to improve paths

Result:

Final shortest distances:
A->A=0, A->B=5, A->C=10, A->D=8
B->A=∞, B->B=0, B->C=∞, B->D=3
C->A=∞, C->B=∞, C->C=0, C->D=1
D->A=∞, D->B=∞, D->C=∞, D->D=0

Annotated Code

DSA Javascript

class Graph {
  constructor(nodes) {
    this.nodes = nodes;
    this.dist = {};
    for (const u of nodes) {
      this.dist[u] = {};
      for (const v of nodes) {
        this.dist[u][v] = u === v ? 0 : Infinity;
      }
    }
  }

  addEdge(u, v, w) {
    this.dist[u][v] = w;
  }

  floydWarshall() {
    const nodes = this.nodes;
    for (const k of nodes) {
      for (const i of nodes) {
        for (const j of nodes) {
          if (this.dist[i][k] + this.dist[k][j] < this.dist[i][j]) {
            this.dist[i][j] = this.dist[i][k] + this.dist[k][j];
          }
        }
      }
    }
  }

  printDistances() {
    for (const i of this.nodes) {
      let line = '';
      for (const j of this.nodes) {
        const val = this.dist[i][j] === Infinity ? '∞' : this.dist[i][j];
        line += `${val}\t`;
      }
      console.log(line.trim());
    }
  }
}

// Driver code
const nodes = ['A', 'B', 'C', 'D'];
const graph = new Graph(nodes);
graph.addEdge('A', 'B', 5);
graph.addEdge('A', 'C', 10);
graph.addEdge('B', 'D', 3);
graph.addEdge('C', 'D', 1);

graph.floydWarshall();
graph.printDistances();

this.dist[u][v] = w;

Set direct edge weight from u to v

for (const k of nodes) {

Use each node k as intermediate point

if (this.dist[i][k] + this.dist[k][j] < this.dist[i][j]) {

Check if path i->k->j is shorter than current i->j

this.dist[i][j] = this.dist[i][k] + this.dist[k][j];

Update shortest distance if better path found

Output

0	5	10	8

∞	0	∞	3

∞	∞	0	1

∞	∞	∞	0

Complexity Analysis

Time: O(n^3) because we check all pairs (i, j) for every intermediate node k

Space: O(n^2) because we store distances between every pair of nodes

vs Alternative: Compared to running Dijkstra from each node (O(n * (m + n log n))), Floyd Warshall is simpler but slower for sparse graphs

Edge Cases

Graph with no edges

Distances remain infinity except zero for same nodes

DSA Javascript

this.dist[u][v] = u === v ? 0 : Infinity;

Graph with single node

Distance to itself is zero, no updates needed

DSA Javascript

this.dist[u][v] = u === v ? 0 : Infinity;

Graph with negative edge weights but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA Javascript

if (this.dist[i][k] + this.dist[k][j] < this.dist[i][j]) {

When to Use This Pattern

When you need shortest paths between all pairs of points and the graph may have negative edges but no negative cycles, use Floyd Warshall to systematically check all intermediate nodes.

Common Mistakes

Mistake: Not initializing distance from a node to itself as zero
Fix: Set dist[u][u] = 0 for all nodes u during initialization

Mistake: Updating distances without checking if intermediate paths improve them
Fix: Use if condition to update only when a shorter path is found

Summary

Finds shortest paths between every pair of nodes in a graph.

Use when you need all pairs shortest paths and graph may have negative edges but no negative cycles.

Check every node as a possible middle stop to improve paths step by step.

Practice

1. What is the main purpose of the Floyd Warshall algorithm in graph theory?

easy

A. To detect cycles in a graph

B. To find the shortest path from a single source to all other vertices

C. To find the shortest paths between all pairs of vertices in a weighted graph

D. To sort vertices in topological order

Solution

1. Step 1: Understand Floyd Warshall's goal

   The Floyd Warshall algorithm calculates shortest paths between every pair of vertices in a weighted graph.

2. Step 2: Differentiate from other algorithms

   Unlike Dijkstra's algorithm which finds shortest paths from one source, Floyd Warshall finds paths for all pairs.

3. Final Answer:

   To find the shortest paths between all pairs of vertices in a weighted graph -> Option C

4. Quick Check:

   All pairs shortest path = Floyd Warshall [OK]

Hint: Floyd Warshall finds shortest paths for all vertex pairs [OK]

Common Mistakes:

• Confusing with Dijkstra's single source shortest path
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in JavaScript given a graph adjacency matrix graph?

easy

A. const dist = graph.map(row => row.slice());

B. const dist = graph.slice();

C. const dist = graph.map(row => row);

D. const dist = [...graph];

Solution

1. Step 1: Understand deep copy necessity

   We need a deep copy of the 2D array so changes to dist do not affect graph.

2. Step 2: Check each option for deep copy

   const dist = graph.map(row => row.slice()); uses map and slice to copy each row array, creating a deep copy. Others create shallow copies.

3. Final Answer:

   const dist = graph.map(row => row.slice()); -> Option A

4. Quick Check:

   Deep copy with map and slice = const dist = graph.map(row => row.slice()); [OK]

Hint: Use map with slice for deep copy of 2D arrays [OK]

Common Mistakes:

• Using shallow copy causing original graph to change
• Using spread operator which copies only top-level array
• Using map without slice copying references

3. What will be the output distance matrix after running Floyd Warshall on the following graph adjacency matrix where Infinity means no direct edge?

const graph = [
  [0, 3, Infinity],
  [2, 0, 5],
  [Infinity, 1, 0]
];

medium

A. [[0, 3, 7], [2, 0, 5], [3, 1, 0]]

B. [[0, 3, 5], [2, 0, 5], [Infinity, 1, 0]]

C. [[0, 3, Infinity], [2, 0, 5], [3, 1, 0]]

D. [[0, 3, 8], [2, 0, 5], [3, 1, 0]]

Solution

1. Step 1: Initialize dist matrix same as graph

   dist = [[0,3,∞],[2,0,5],[∞,1,0]]

2. Step 2: Update dist using Floyd Warshall iterations

   Check paths through each vertex k=0,1,2:
   k=0: dist[2][0] = min(∞, dist[2][0]+dist[0][0])=∞ no change
   k=1: dist[0][2] = min(∞, dist[0][1]+dist[1][2])=3+5=8
   dist[2][0] = min(∞, dist[2][1]+dist[1][0])=1+2=3
   k=2: no shorter paths found
   Final dist = [[0,3,8],[2,0,5],[3,1,0]]

3. Final Answer:

   [[0, 3, 8], [2, 0, 5], [3, 1, 0]] -> Option D

4. Quick Check:

   Updated shortest paths matrix = [[0, 3, 8], [2, 0, 5], [3, 1, 0]] [OK]

Hint: Check all intermediate vertices to update shortest paths [OK]

Common Mistakes:

• Not updating paths through intermediate vertices
• Confusing Infinity with zero
• Missing updates for indirect paths

4. Identify the error in this Floyd Warshall implementation snippet:

for (let k = 0; k < V; k++) {
  for (let i = 0; i < V; i++) {
    for (let j = 0; j < V; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

medium

A. Missing check if dist[i][k] or dist[k][j] is Infinity before addition

B. The loops should be reversed: i, j, then k

C. No error, the code is correct

D. The condition should use <= instead of <

Solution

1. Step 1: Analyze addition of distances

   Adding dist[i][k] + dist[k][j] without checking if either is Infinity can cause incorrect results or overflow.

2. Step 2: Identify missing Infinity checks

   Before adding, must ensure dist[i][k] !== Infinity and dist[k][j] !== Infinity to avoid invalid sums.

3. Final Answer:

   Missing check if dist[i][k] or dist[k][j] is Infinity before addition -> Option A

4. Quick Check:

   Check Infinity before sum to avoid errors [OK]

Hint: Always check for Infinity before adding distances [OK]

Common Mistakes:

• Ignoring Infinity causing wrong updates
• Changing loop order unnecessarily
• Using <= instead of < causing redundant updates

5. Given a weighted directed graph with possible negative edges but no negative cycles, how does Floyd Warshall detect the presence of a negative cycle after running the algorithm?

hard

A. By checking if any dist[i][j] is Infinity

B. By checking if any diagonal element dist[i][i] becomes negative

C. By verifying if the sum of all distances is zero

D. By checking if any dist[i][j] is negative for i != j

Solution

1. Step 1: Understand negative cycle effect on dist matrix

   Negative cycles cause the shortest path from a vertex to itself to become negative.

2. Step 2: Check diagonal elements after Floyd Warshall

   If any dist[i][i] < 0, it means a negative cycle exists involving vertex i.

3. Final Answer:

   By checking if any diagonal element dist[i][i] becomes negative -> Option B

4. Quick Check:

   Negative cycle detected if dist[i][i] < 0 [OK]

Hint: Check diagonal dist[i][i] for negativity to find negative cycles [OK]

Common Mistakes:

• Checking off-diagonal elements for negative cycles
• Confusing Infinity with negative cycles
• Assuming sum of distances indicates cycles