2020-05-03 01:03:10 +05:30
|
|
|
// starting at s
|
2023-10-03 23:08:19 +02:00
|
|
|
function solve(graph, s) {
|
2020-10-01 23:05:36 +05:30
|
|
|
const solutions = {}
|
2020-05-04 22:31:34 +02:00
|
|
|
solutions[s] = []
|
|
|
|
|
solutions[s].dist = 0
|
2020-05-03 01:03:10 +05:30
|
|
|
|
2020-05-04 22:31:34 +02:00
|
|
|
while (true) {
|
2020-10-01 23:05:36 +05:30
|
|
|
let p = null
|
|
|
|
|
let neighbor = null
|
|
|
|
|
let dist = Infinity
|
2020-05-04 22:31:34 +02:00
|
|
|
|
2020-10-01 23:05:36 +05:30
|
|
|
for (const n in solutions) {
|
2023-10-03 23:08:19 +02:00
|
|
|
if (!solutions[n]) {
|
|
|
|
|
continue
|
|
|
|
|
}
|
2020-10-01 23:05:36 +05:30
|
|
|
const ndist = solutions[n].dist
|
|
|
|
|
const adj = graph[n]
|
2020-05-04 22:31:34 +02:00
|
|
|
|
2020-10-01 23:05:36 +05:30
|
|
|
for (const a in adj) {
|
2023-10-03 23:08:19 +02:00
|
|
|
if (solutions[a]) {
|
|
|
|
|
continue
|
|
|
|
|
}
|
2020-05-04 22:31:34 +02:00
|
|
|
|
2020-10-01 23:05:36 +05:30
|
|
|
const d = adj[a] + ndist
|
2020-05-04 22:31:34 +02:00
|
|
|
if (d < dist) {
|
|
|
|
|
p = solutions[n]
|
|
|
|
|
neighbor = a
|
|
|
|
|
dist = d
|
2020-05-03 01:03:10 +05:30
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
2020-05-04 22:31:34 +02:00
|
|
|
|
|
|
|
|
// no more solutions
|
|
|
|
|
if (dist === Infinity) {
|
|
|
|
|
break
|
2020-05-03 01:03:10 +05:30
|
|
|
}
|
2020-05-04 22:31:34 +02:00
|
|
|
|
|
|
|
|
// extend parent's solution path
|
|
|
|
|
solutions[neighbor] = p.concat(neighbor)
|
|
|
|
|
// extend parent's cost
|
|
|
|
|
solutions[neighbor].dist = dist
|
2020-05-03 01:03:10 +05:30
|
|
|
}
|
2020-05-04 22:31:34 +02:00
|
|
|
|
|
|
|
|
return solutions
|
2020-05-03 01:03:10 +05:30
|
|
|
}
|
|
|
|
|
|
2021-10-10 17:55:08 +02:00
|
|
|
export { solve }
|
