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 }

// // create graph
// const graph = {}

// const layout = {
//   R: ['2'],
//   2: ['3', '4'],
//   3: ['4', '6', '13'],
//   4: ['5', '8'],
//   5: ['7', '11'],
//   6: ['13', '15'],
//   7: ['10'],
//   8: ['11', '13'],
//   9: ['14'],
//   10: [],
//   11: ['12'],
//   12: [],
//   13: ['14'],
//   14: [],
//   15: []
// }

// // convert uni-directional to bi-directional graph
// let  graph = {
//     a: {e:1, b:1, g:3},
//     b: {a:1, c:1},
//     c: {b:1, d:1},
//     d: {c:1, e:1},
//     e: {d:1, a:1},
//     f: {g:1, h:1},
//     g: {a:3, f:1},
//     h: {f:1}
// };

// for (const id in layout) {
//   if (!graph[id]) { graph[id] = {} }
//   layout[id].forEach(function (aid) {
//     graph[id][aid] = 1
//     if (!graph[aid]) { graph[aid] = {} }
//     graph[aid][id] = 1
//   })
// }

// // choose start node
// const start = '10'
// // get all solutions
// const solutions = solve(graph, start)

// // for s in solutions..
// ' -> ' + s + ': [' + solutions[s].join(', ') + ']   (dist:' + solutions[s].dist + ')'

// From '10' to
//  -> 2: [7, 5, 4, 2]   (dist:4)
//  -> 3: [7, 5, 4, 3]   (dist:4)
//  -> 4: [7, 5, 4]   (dist:3)
//  -> 5: [7, 5]   (dist:2)
//  -> 6: [7, 5, 4, 3, 6]   (dist:5)
//  -> 7: [7]   (dist:1)
//  -> 8: [7, 5, 4, 8]   (dist:4)
//  -> 9: [7, 5, 4, 3, 13, 14, 9]   (dist:7)
//  -> 10: []   (dist:0)
//  -> 11: [7, 5, 11]   (dist:3)
//  -> 12: [7, 5, 11, 12]   (dist:4)
//  -> 13: [7, 5, 4, 3, 13]   (dist:5)
//  -> 14: [7, 5, 4, 3, 13, 14]   (dist:6)
//  -> 15: [7, 5, 4, 3, 6, 15]   (dist:6)
//  -> R: [7, 5, 4, 2, R]   (dist:5)