Javascript Coding Test Course, Floyd-Warshall

Author: [Your Name]

Written on: [Date]

Table of Contents

  1. 1. Introduction
  2. 2. Problem Description
  3. 3. Understanding the Floyd-Warshall Algorithm
  4. 4. JavaScript Implementation
  5. 5. Time Complexity
  6. 6. Conclusion

1. Introduction

Algorithm problems are frequently presented in coding tests, and the ability to understand and implement various algorithms is important. This course will cover the Floyd-Warshall algorithm and teach how to implement it in JavaScript. The Floyd-Warshall algorithm is useful for finding the shortest paths between all pairs of vertices in a graph, particularly suited for large graphs.

2. Problem Description

Problem: Write an algorithm to find the shortest paths between all vertices in a given directed graph. The graph consists of edges with weights. If there is no path between two vertices, the value of the shortest path is handled as infinity.


Input:
- Number of vertices N (1 ≤ N ≤ 100)
- Number of edges M (1 ≤ M ≤ 10000)
- Edge information of M edges (A, B, C): weight C from A to B

Output:
- Print an N x N matrix representing the lengths of the shortest paths between the destination vertices.

3. Understanding the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm uses dynamic programming techniques to compute the shortest paths between all pairs. The algorithm includes the following steps:

  1. Initialize distance values between all pairs of vertices (i, j). Set weights for directly connected vertices and infinity (INFINITY) for non-connected ones.
  2. Set each vertex as an intermediate vertex and check the shortest path from i to j. Using k as the intermediate vertex, check if the path i -> k -> j is shorter than the direct path i -> j.
  3. Repeat this process for all vertices.

By doing this, we can ultimately find the shortest paths between all pairs of vertices.


function floydWarshall(graph) {
  const dist = JSON.parse(JSON.stringify(graph)); // Copy the graph to initialize the distance matrix

  const n = graph.length; // Number of vertices
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}

4. JavaScript Implementation

Now let’s implement the Floyd-Warshall algorithm in JavaScript. First, we will handle input, initialize the graph, and then write a function to calculate the shortest paths:


function initializeGraph(N, edges) {
  const graph = Array.from({ length: N }, () => Array(N).fill(Infinity));
  for (let i = 0; i < N; i++) {
    graph[i][i] = 0; // The case for going to itself is 0
  }

  edges.forEach(([A, B, C]) => {
    graph[A][B] = Math.min(graph[A][B], C); // Update to the minimum weight if there are multiple edges
  });

  return graph;
}

// Main function to solve the problem
function solve(N, M, edges) {
  const graph = initializeGraph(N, edges);
  const shortestPaths = floydWarshall(graph);

  console.log("Shortest Path Matrix:");
  shortestPaths.forEach(row => console.log(row.join(" ")));
}

5. Time Complexity

The time complexity of the Floyd-Warshall algorithm is O(N^3). This is because a triple loop is used to check each pair of vertices when N is the number of vertices. Therefore, it can be efficiently used when the number of vertices is reasonably small (100 or less), but for graphs with hundreds of vertices, other algorithms should be considered.

6. Conclusion

In this course, we explored the theory of the Floyd-Warshall algorithm and how to implement it in JavaScript. By understanding the algorithm and practicing the code implementation, we can enhance our problem-solving skills in coding tests. Next time, we will cover even more diverse algorithms.