What is Dijkstra's Algorithm?
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants.wikipedia
Scenario
Basically, Dijkstra's algorithm determine the fastest path from one location to another. To demonstrate a real life example of using this algorithm. Here I will present an example of Governors Island in New York City, New York. In this example, I will exclude all other factors, such as speed, weather, construction, etc.
I took a screenshot of the Governors Island from Google map; and then I marked and drew a couple of places and routes using photoshop. Using the Google map, I was able to measure the distance between each locations. So I also labeled the distances.
Problem
I went to Governors Island in summer 2017 and 2019. When I was there, I have the following questions:
What is the shortest path to get to Bike Rentals from Soissons Landing?
After I rent a bike, I want to ride to Kayak Dock. What is the fastest path from Bike Rentals to Kayak Docke?
After a fun ride, I need to go to Picnic Point where I can have something to eat. What is the shortest path from Kayak Dock to Picnic Point?
After having a picnic, I realize I need to return the bike as soon as possible, otherwise I have to pay for another hour (approximately $48). What is the shortest path from Picnic Point to Bike Rentals?
After we implemented the solution, it should answer the above questions.
Graph
First of all, we need some kind of data. And the graph data already presented on the map; we need to convert it to object in JavaScript. For simplicity, readability, and error-free; I store the name of the locations in a constant variable.
const NAME = {
SOISSONS_LANDING: 'Soissons Landing',
CASTLE_WILLIAMS: 'Castle Williams',
KAYAK_DOCK: 'Kayak Dock',
COLONELS_ROW: 'Colonels Row',
NOLAN_PARK: 'Nolan Park',
BIKE_RENTALS: 'Bike Rentals',
TEACHING_GARDEN: 'Teaching Garden',
YANKEE_PIER: 'Yankee Pier',
THE_HILLS: 'The Hills',
PICNIC_POINT: 'Picnic Point'
};
Next, let's construct our graph data. It stores the location name and the next location name and distance. For instance, from Soissons Landing, we can reach four locations: Castle Williams, Colonels Row, Nolan Park, and Kayak Dock. It should be more like this.
const soissonLanding = {
castleWilliams: 1376,
colonelsRow: 1513,
nolanPark: 1200,
kayakDock: 1063
};
We have more than one location, so we are going to store them in a variable called graph.
const graph = {
[NAME.SOISSONS_LANDING]: {
[NAME.CASTLE_WILLIAMS]: 1376,
[NAME.COLONELS_ROW]: 1513,
[NAME.NOLAN_PARK]: 1200,
[NAME.KAYAK_DOCK]: 1063,
},
[NAME.CASTLE_WILLIAMS]: {
[NAME.SOISSONS_LANDING]: 1376,
[NAME.COLONELS_ROW]: 1143,
},
[NAME.COLONELS_ROW]: {
[NAME.SOISSONS_LANDING]: 1513,
[NAME.BIKE_RENTALS]: 1176,
[NAME.CASTLE_WILLIAMS]: 1143,
[NAME.NOLAN_PARK]: 1700,
},
[NAME.NOLAN_PARK]: {
[NAME.SOISSONS_LANDING]: 1200,
[NAME.COLONELS_ROW]: 1700,
[NAME.KAYAK_DOCK]: 820,
[NAME.YANKEE_PIER]: 1676,
},
[NAME.KAYAK_DOCK]: {
[NAME.SOISSONS_LANDING]: 1063,
[NAME.NOLAN_PARK]: 820,
},
[NAME.BIKE_RENTALS]: {
[NAME.COLONELS_ROW]: 1176,
[NAME.YANKEE_PIER]: 652,
[NAME.TEACHING_GARDEN]: 1117,
},
[NAME.YANKEE_PIER]: {
[NAME.BIKE_RENTALS]: 652,
[NAME.NOLAN_PARK]: 1676,
[NAME.TEACHING_GARDEN]: 1049,
[NAME.PICNIC_POINT]: 2862,
},
[NAME.TEACHING_GARDEN]: {
[NAME.BIKE_RENTALS]: 1117,
[NAME.YANKEE_PIER]: 1049,
[NAME.THE_HILLS]: 1053,
[NAME.PICNIC_POINT]: 1796,
},
[NAME.THE_HILLS]: {
[NAME.TEACHING_GARDEN]: 1053,
[NAME.PICNIC_POINT]: 1243,
},
[NAME.PICNIC_POINT]: {
[NAME.THE_HILLS]: 1243,
[NAME.TEACHING_GARDEN]: 1796,
[NAME.YANKEE_PIER]: 2862,
},
};
Approach
From the start location, loop through each path, and keep the minimum distance path; and at the same time, keep a reference of both locations (current location to next location, next location to previous location; for example: parent <-> child). Also keep a list of visited locations; at this point, start location is already visited. So set start location as visited.
Repeat this step on possible paths that is unvisited and is the minimum distance path.
At the end, we have the minimum distance from start location to the finish location. Now we can retrieve the shortest path by using the references that we kept earlier.
Solution
/**
* @typeof {object} ShortestPathResult
* @param {number} distance
* @param {string[]} paths
*/
/**
* Get the shortest path from start location to finish location
*
* @param {object} graph
* @param {string} start
* @param {string} finish
*
* @return {ShortestPathResult}
*/
const shortestPath = (graph, start, finish) => {
// RETURN UNDEFINED
// IF START OR FINISH LOCATION DOES NOT EXISTS
if (graph[start] === undefined || graph[finish] === undefined) {
return;
}
// KEEP TRACK OF MINIMUM DISTANCE FOR EACH POSSIBLE PATH
const distances = {
[finish]: Infinity,
...graph[start],
};
// KEEP REFERENCE OF
// CURRENT LOCATION TO NEXT LOCATION
// NEXT LOCATION TO PREVIOUS LOCATION
// EXAMPLE: PARENT <-> CHILD
const parents = {
[finish]: null,
};
// CREATE A REFERENCE FOR THE START LOCATION AND NEXT LOCATIONS
for (const child in graph[start]) {
parents[child] = start;
}
// KEEP A LIST OF LOCATIONS THAT HAS BEEN PROCESSED
// WE SKIP START AND FINISH LOCATION
const visited = { [start]: true, [finish]: true };
// GET THE UNVISITED MINIMUM DISTANCE LOCATION
let node = getMinimumDistanceLocation(distances, visited);
while (node !== null) {
// GET THE CURRENT DISTANCE
let currentDistance = distances[node];
// GET ITS ADJACENT LOCATIONS
const locations = graph[node];
for (const name in locations) {
// TOTAL DISTANCE = CURRENT DISTANCE + NEXT LOCATION DISTANCE
let totalDistance = currentDistance + locations[name];
if (name !== start && (distances[name] === undefined || totalDistance < distances[name])) {
// KEEP THE SHORTEST DISTANCE
distances[name] = totalDistance;
parents[name] = node;
}
}
// SET THIS LOCATION AS VISITED
visited[node] = true;
// GET THE NEXT UNVISITED MINIMUM DISTANCEE PATH
node = getMinimumDistanceLocation(distances, visited);
}
// HOLD SHORTEST PATH'S LOCATIONS
const paths = [];
// RETRIEVE THE PATH IN REVERSE ORDER
let previousNode = finish;
// BACK TRACE TO THE START LOCATION
while (previousNode) {
paths.unshift(previousNode);
previousNode = parents[previousNode];
}
// RETURN THE DISTANCE AND THE SHORTEST PATH
return {
distance: distances[finish] || 0,
paths,
};
};
/**
* Get the minimum distance of the given locations
*
* @param {object} locations // Ex. { A: 2, B: 3, C: 4}
* @param {object} visited // Ex. { B: true }
* @return {string} the name of the location
*/
const getMinimumDistanceLocation = (locations, visited) => {
let minimum = null;
for (const name in locations) {
if (!visited[name] && (minimum === null || locations[name] < locations[minimum])) {
minimum = name;
}
}
return minimum;
};
Answers to the Questions
What is the shortest path to get to Bike Rentals from Soissons Landing?
shortestPath(graph, NAME.SOISSONS_LANDING, NAME.BIKE_RENTALS);
// Output
{
distance: 2689,
paths: [
'Soissons Landing',
'Colonels Row',
'Bike Rentals'
]
}
After I rent a bike, I want to ride to Kayak Dock. What is the fastest path from Bike Rentals to Kayak Docke?
shortestPath(graph, NAME.BIKE_RENTALS, NAME.KAYAK_DOCK);
// Output
{
distance: 3148,
paths: [
'Bike Rentals',
'Yankee Pier',
'Nolan Park',
'Kayak Dock'
]
}
After a fun ride, I need to go to Picnic Point where I can have something to eat. What is the shortest path from Kayak Dock to Picnic Point?
shortestPath(graph, NAME.KAYAK_DOCK, NAME.PICNIC_POINT);
// Output
{
distance: 5341,
paths: [
'Kayak Dock',
'Nolan Park',
'Yankee Pier',
'Teaching Garden',
'Picnic Point'
]
}
After having a picnic, I realize I need to return the bike as soon as possible, otherwise I have to pay for another hour (approximately $48). What is the shortest path from Picnic Point to Bike Rentals?
shortestPath(graph, NAME.PICNIC_POINT, NAME.BIKE_RENTALS);
// Output
{
distance: 2913,
paths: [
'Picnic Point',
'Teaching Garden',
'Bike Rentals'
]
}
Real World
In real world, it would become more complicated. There are bewildering number of paths. Each path are connected to each other in intersection (a dot/point in the picture below).
