DijkstraSmallestPath.js

// 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 }