Skip to content

Instantly share code, notes, and snippets.

@hungneox
Forked from stella-yc/dijkstra.js
Created December 17, 2020 05:09
Show Gist options
  • Save hungneox/1541f1b4d0ca4048ef18f9b2800928ac to your computer and use it in GitHub Desktop.
Save hungneox/1541f1b4d0ca4048ef18f9b2800928ac to your computer and use it in GitHub Desktop.
Dijkstra's Algorithm in Javascript using a weighted graph
const problem = {
start: {A: 5, B: 2},
A: {C: 4, D: 2},
B: {A: 8, D: 7},
C: {D: 6, finish: 3},
D: {finish: 1},
finish: {}
};
const lowestCostNode = (costs, processed) => {
return Object.keys(costs).reduce((lowest, node) => {
if (lowest === null || costs[node] < costs[lowest]) {
if (!processed.includes(node)) {
lowest = node;
}
}
return lowest;
}, null);
};
// function that returns the minimum cost and path to reach Finish
const dijkstra = (graph) => {
// track lowest cost to reach each node
const costs = Object.assign({finish: Infinity}, graph.start);
// track paths
const parents = {finish: null};
for (let child in graph.start) {
parents[child] = 'start';
}
// track nodes that have already been processed
const processed = [];
let node = lowestCostNode(costs, processed);
while (node) {
let cost = costs[node];
let children = graph[node];
for (let n in children) {
let newCost = cost + children[n];
if (!costs[n]) {
costs[n] = newCost;
parents[n] = node;
}
if (costs[n] > newCost) {
costs[n] = newCost;
parents[n] = node;
}
}
processed.push(node);
node = lowestCostNode(costs, processed);
}
let optimalPath = ['finish'];
let parent = parents.finish;
while (parent) {
optimalPath.push(parent);
parent = parents[parent];
}
optimalPath.reverse();
const results = {
distance: costs.finish,
path: optimalPath
};
return results;
};
console.log(dijkstra(problem));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment