Skip to content

Instantly share code, notes, and snippets.

@dengjonathan
Created February 27, 2018 04:12
Show Gist options
  • Save dengjonathan/519bff298439f6d12218cb13a871cfe2 to your computer and use it in GitHub Desktop.
Save dengjonathan/519bff298439f6d12218cb13a871cfe2 to your computer and use it in GitHub Desktop.
djiksta's algorithm
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: {}
};
const getMin = (queue, distances) => {
let distance = Infinity;
for (let i = 0; i < queue.length; i++) {
const node = queue[i];
if (distances[node] < distance) {
result = i;
distance = distances[node];
}
}
return result;
}
const getEntirePath = (previousNodes) => {
const result = [];
let current = 'finish';
while (current) {
console.log(result)
result.unshift(current);
if (current === 'start') {
return result;
}
current = previousNodes[current];
}
return null;
}
const djikstra = (graph) => {
const graphKeys = Object.keys(graph);
const distances = graphKeys.reduce((dists, key) => (
Object.assign(dists, { [key]: Infinity })
), {});
distances['start'] = 0;
const previousNode = graphKeys.reduce((prevs, key) => (
Object.assign(prevs, { [key]: undefined })
), {});
const unvisited = graphKeys.slice();
while (unvisited.length) {
// get closest node and remove it from unvisited
const currentIndex = getMin(unvisited, distances);
const currentNode = unvisited[currentIndex];
unvisited.splice(currentIndex, 1);
const edges = graph[currentNode];
for (neighbor in edges) {
const distToNeighbor = edges[neighbor];
const tentativeDist = distances[currentNode] + distToNeighbor;
if (neighbor === 'finish') {
previousNode[neighbor] = currentNode;
return getEntirePath(previousNode);
}
if (tentativeDist < distances[neighbor]) {
distances[neighbor] = tentativeDist;
previousNode[neighbor] = currentNode;
}
}
}
return null;
}
console.log(
djikstra(problem)
);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment