Skip to content

Instantly share code, notes, and snippets.

@MoeweX
Forked from stella-yc/dijkstra.js
Last active July 25, 2022 20:50
Show Gist options
  • Save MoeweX/ab98efee9435b47529e3a6cb50c5b605 to your computer and use it in GitHub Desktop.
Save MoeweX/ab98efee9435b47529e3a6cb50c5b605 to your computer and use it in GitHub Desktop.
Dijkstra's Algorithm in Javascript using a Weighted Graph
// Changes to original version
// 1. Calculate the distance between any nodes in the dataset, without needing to edit the problem dictionary.
// 2. Prevent algorithm from going back to start node if loops exist in graph (e.g., in problem below)
const problem = {
start: {A: 5, B: 2},
A: {start: 1, C: 4, D: 2},
B: {A: 8, D: 7},
C: {D: 6, finish: 3},
D: {finish: 1},
finish: {}
};
function log(message) {
const logging = false;
if (logging) {
console.log(message);
}
}
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, startNodeName, endNodeName) => {
// track the lowest cost to reach each node
let costs = {};
costs[endNodeName] = "Infinity";
costs = Object.assign(costs, graph[startNodeName]);
// track paths
const parents = {endNodeName: null};
for (let child in graph[startNodeName]) {
parents[child] = startNodeName;
}
// 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) {
if (String(n) === String(startNodeName)) {
log("WE DON'T GO BACK TO START");
} else {
log("StartNodeName: " + startNodeName);
log("Evaluating cost to node " + n + " (looking from node " + node + ")");
log("Last Cost: " + costs[n]);
let newCost = cost + children[n];
log("New Cost: " + newCost);
if (!costs[n] || costs[n] > newCost) {
costs[n] = newCost;
parents[n] = node;
log("Updated cost und parents");
} else {
log("A shorter path already exists");
}
}
}
processed.push(node);
node = lowestCostNode(costs, processed);
}
let optimalPath = [endNodeName];
let parent = parents[endNodeName];
while (parent) {
optimalPath.push(parent);
parent = parents[parent];
}
optimalPath.reverse();
const results = {
distance: costs[endNodeName],
path: optimalPath
};
return results;
};
//console.log(dijkstra(problem, "start", "finish"));
//console.log(dijkstra(problem, "A", "B"));
//console.log(dijkstra(problem, "A", "start"));
@ttrulock1
Copy link

Is this for undirected graph?

It is a directed graph.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment