Floyd Warshall All Pairs Shortest Path in DSA Typescript - Build from Scratch

Floyd Warshall All Pairs Shortest Path

📖 Scenario: You are working as a city planner. You have a map of cities connected by roads with distances. You want to find the shortest distance between every pair of cities to plan the best routes.

🎯 Goal: Build a program that uses the Floyd Warshall algorithm to find the shortest paths between all pairs of cities in a given map.

📋 What You'll Learn

Create a 2D array called dist representing the distances between cities.

Create a variable numCities to store the number of cities.

Implement the Floyd Warshall algorithm using three nested for loops with variables k, i, and j.

Update the dist array with the shortest distances.

Print the final dist array showing shortest distances between all city pairs.

💡 Why This Matters

🌍 Real World

City planners and GPS systems use all pairs shortest path algorithms to find the best routes between locations.

💼 Career

Understanding Floyd Warshall helps in roles involving route optimization, network analysis, and logistics planning.

1

Create the initial distance matrix

Create a 2D array called dist with these exact values representing distances between 4 cities. Use Infinity where there is no direct road: [[0, 5, Infinity, 10], [Infinity, 0, 3, Infinity], [Infinity, Infinity, 0, 1], [Infinity, Infinity, Infinity, 0]]

DSA Typescript

// Create the 2D array dist with the given distances
// Your code here

Hint

Use const dist: number[][] = [...] to create the matrix exactly as shown.

2

Set the number of cities

Create a variable called numCities and set it to the number of cities in the dist array.

DSA Typescript

const dist: number[][] = [
  [0, 5, Infinity, 10],
  [Infinity, 0, 3, Infinity],
  [Infinity, Infinity, 0, 1],
  [Infinity, Infinity, Infinity, 0]
];
// Create numCities and set it to the length of dist
// Your code here

Hint

Use const numCities: number = dist.length; to get the number of cities.

3

Implement the Floyd Warshall algorithm

Use three nested for loops with variables k, i, and j from 0 to numCities. Inside the innermost loop, update dist[i][j] to the minimum of its current value and dist[i][k] + dist[k][j].

DSA Typescript

const dist: number[][] = [
  [0, 5, Infinity, 10],
  [Infinity, 0, 3, Infinity],
  [Infinity, Infinity, 0, 1],
  [Infinity, Infinity, Infinity, 0]
];

const numCities: number = dist.length;

// Implement Floyd Warshall algorithm using for loops
// Your code here

Hint

Use three nested loops and update dist[i][j] if a shorter path is found through k.

4

Print the shortest distance matrix

Print the dist array after running the Floyd Warshall algorithm. Use console.log(dist) to display the final shortest distances between all pairs of cities.

DSA Typescript

const dist: number[][] = [
  [0, 5, Infinity, 10],
  [Infinity, 0, 3, Infinity],
  [Infinity, Infinity, 0, 1],
  [Infinity, Infinity, Infinity, 0]
];

const numCities: number = dist.length;

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

// Print the dist array
// Your code here

Hint

Use console.log(dist) to print the final matrix.