Sandbox::https://github.com/sibalonecoding-code/JavaScript/blob/master/Graphs/DijkstraSmallestPath.js

Repository navigation

47 lines (39 loc) · 847 Bytes

// starting at s

function solve(graph, s) {

const solutions = {}

solutions[s] = []

solutions[s].dist = 0

while (true) {

let p = null

let neighbor = null

let dist = Infinity

for (const n in solutions) {

if (!solutions[n]) {

continue

}

const ndist = solutions[n].dist

const adj = graph[n]

for (const a in adj) {

if (solutions[a]) {

continue

}

const d = adj[a] + ndist

if (d < dist) {

p = solutions[n]

neighbor = a

dist = d

}

// no more solutions

if (dist === Infinity) {

break

}

// extend parent's solution path

solutions[neighbor] = p.concat(neighbor)

// extend parent's cost

solutions[neighbor].dist = dist

}

return solutions

}

export { solve }