Floyd-Warshall_algorithm.js

/**
* Let's say we want to find the shortest path among *all* pairs
* of U.S. cities. For example, let's assume (for the sake of argument)
* that Seattle is 200 miles from Chicago, 300 miles from Miami, etc.
*/
const cities = [
  {
    name: 'Seattle',
    edges: [
      ['Chicago', 200],
      ['Miami', 300]
    ]
  },
  {
    name: 'Alaska',
    edges: [
      ['Seattle', 200]
    ]
  },
  {
    name: 'Chicago',
    edges: [
      ['Miami', 400]
    ]
  },
  {
    name: 'Key West',
    edges: [
      ['Seattle', 1000]
    ]
  },
  {
    name: 'Miami',
    edges: [
      ['Key West', 200],
      ['Seattle', 900]
    ]
  }
];

/** I presented the cities list as an array of objects because that makes it
* easy to understand, but the algorithm expects a 2D matrix. Here we
* build a table where each row represents a starting city and each column
* is a destination.
*
* In this example, the first row represents Seattle and the third row represents
* Chicago. To the best of our knowledge at first (simply looking at the paths
* leading out Seattle), the best route to Chicago is 200 miles:

 [
    [0, Infinity, 200, 500, 300],
    [Infinity, 200, 500, 300],
    // ...
  ]
*/

const buildCityDistanceTable = (cities) => {
  const { length } = cities;

  // I'm doing this because of the way I chose to format the data initially.
  // I use it to deterministically map edges to verticies. If you start off
  // with a 2D matrix, this step is unnecessary.
  const mapCityNameToIndex = cities.reduce((map, city, index) => {
    map[city.name] = index;
    return map;
  }, {});

  // Create the 2D matrix where each row corresponds to a
  // source node and each column corresponds to a destination.
  const distanceTable = new Array(length)
    .fill(null)
    .map((item, index) => {
      // If at first we don't know the distance between a given city and other
      // cities, assume the distance is infinite.
      const distanceToOtherCities = new Array(length).fill(Infinity);

      // If the current node has edges to other nodes (cities), account
      // for those relative distances.
      const { edges } = cities[index];

      for (const [edgeName, distance] of edges) {
        const otherCityIndex = mapCityNameToIndex[edgeName];
        distanceToOtherCities[otherCityIndex] = distance;
      }

      // We know the distance from a location to itself is 0.
      distanceToOtherCities[index] = 0;
      return distanceToOtherCities;
    });

    return distanceTable;
};

const allShortestPaths = (distanceTable) => {
  const totalNodes = distanceTable.length;
  
  // Loop once for each available node (a.k.a. vertex). At each iteration,
  // we calculate the shortest path for nodes 0...k.
  for (let k = 0; k < totalNodes; k++) {
    for (let source = 0; source < totalNodes; source++) {
      // For each destination node
      for (let dest = 0; dest < totalNodes; dest++) {
        const currentShortest = distanceTable[source][dest];
        const maybeNewShortest = distanceTable[source][k] + distanceTable[k][dest];

        // Greedily walk through the distance table, building on previous sub-problems
        if (currentShortest > maybeNewShortest) {
          distanceTable[source][dest] = maybeNewShortest;
        }
      }
    }
  }
  return distanceTable;
};

const cityTable = buildCityDistanceTable(cities);
allShortestPaths(cityTable);