The Floyd-Warshall algorithm is a dynamic programming algorithm (you will learn more about dynamic programming in Chapter 14, Algorithm Design and Techniques) to calculate all the shortest paths on a graph. With this algorithm, we can find the shortest path from all the sources to all the vertices.
The Floyd-Warshall algorithm is given as follows:
const floydWarshall = graph => { const dist = []; const { length } = graph; for (let i = 0; i < length; i++) { // {1} dist[i] = []; for (let j = 0; j < length; j++) { if (i === j) { dist[i][j] = 0; // {2} } else if (!isFinite(graph[i][j])) { dist[i][j] = Infinity; // {3} } else { dist[i][j] = graph[i][j]; // {4} } } } for (let k = 0; k < length; k++) { // {5} for (let ...
