Skip to content

Instantly share code, notes, and snippets.

@Deifinger
Last active June 21, 2018 14:16
Show Gist options
  • Save Deifinger/2a9f33bdd33ac838c72167d054d37224 to your computer and use it in GitHub Desktop.
Save Deifinger/2a9f33bdd33ac838c72167d054d37224 to your computer and use it in GitHub Desktop.
Dijkstra's algorithm on JavaScript (es6)
const start = 'ml'
const graph = {
ml: {
zp: 30,
dp: 120,
},
zp: {
kv: 300,
dp: 70,
},
dp: {
kv: 250,
},
kv: {}
}
const costs = Object.keys(graph).filter(v => v !== start).reduce((obj, v) => {
obj[v] = Infinity
return obj
}, {})
const parents = Object.keys(costs).reduce((obj, v) => {
obj[v] = []
return obj
}, {})
const goPoint = (next, current, cost, parent) => {
console.log(costs)
if (costs[next] > cost + current) {
costs[next] = cost + current
if(parents[parent]) parents[next].push( ...parents[parent] )
parents[next].push(parent)
if(graph[next]) {
getWay(graph[next], costs[next], next)
}
}
}
const getWay = (node, cost, parent) => {
for (let i in node) {
goPoint(i, node[i], cost, parent)
}
}
getWay(graph.ml, 0, start)
console.log(costs)
console.log(parents)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment