Skip to content

Instantly share code, notes, and snippets.

@codyromano
Last active August 2, 2018 05:52
Show Gist options
  • Save codyromano/fa71c236a3640862b634d97cdee8dd33 to your computer and use it in GitHub Desktop.
Save codyromano/fa71c236a3640862b634d97cdee8dd33 to your computer and use it in GitHub Desktop.
/**
* 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment