Solving the "All Shortest Paths" Problem in JavaScript (ES8)

The Floyd–Warshall algorithm is a nifty way to discover all shortest paths between all pairs of verticies in a weighted, directed graph.

In the JavaScript code below, I use the example of computing routes among major U.S. cities. It's a bit verbose, but if you're new to Floyd-Warshall, the comments may help you understand what the algorithm is doing.

If you're not familiar with graph theory or dynamic programming, consider brushing up on the basics here and here because they'll make the code a lot clearer.

/**
* 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);
Cody Romano

Cody Romano

I'm a front-end software engineer in Amazon's R&D lab. I help research and develop confidential devices.

Read More