Вот проблема, которую можно смоделировать с помощью ориентированного графа с разными затратами на каждом ребре.
Наш вход — это массив ребер.
const edges = [['A', 'B', 20], ['B', 'C', 10], ['A', 'C', 50], ['B', 'D', 5], ['D', 'C', 2]]
['A', 'B', 20],
это означает, что от A
к B
стоимость равна 20. Я хотел написать функцию, которая возвращает путь между данным местом и другим местом, стоимость которого меньше определенной суммы. Обратите внимание, что есть без циклов в этом графике.
В этом случае, если стартовое место A
и пункт назначения C
тогда есть три пути
path 1: A => C - cost 50
path 2: A => B => C - cost 30
path 3: A => B => D => C - cost 27
Если мы говорим, что стоимость должна быть меньше 40, поэтому функция должна возвращать кратчайший путь, который A, B, C
Вот моя попытка:
function getShortestPath(edges, start, end, maxCost) {
const visited = new Map()
const graph = edges.reduce((map, [start, end, cost]) => {
if(map.has(start)) {
map.get(start).push([end, cost])
} else {
map.set(start, [[end, cost]])
}
return map
}, new Map())
const queue = [[start, 0]]
for(const [node, costSofar] of queue) {
if(node === end && costSofar <= maxCost) {
let pointer = node
const path = []
while(pointer) {
path.push(pointer)
pointer = visited.get(pointer)
}
return path.reverse()
}
graph.get(node).forEach(([dest, localCost]) => {
if(localCost + costSofar <= maxCost) {
if(!visited.has(dest)) visited.set(dest, node)
queue.push([dest, localCost + costSofar])
}
})
}
return []
}
Поэтому я использую список смежности для представления графа, т.е.
{
A: [['B', 20], ['C', 50]]
B: [['C', 10], ['D', 5]]
D: [['C', 2]]
}
а затем я использую поиск в ширину, чтобы исследовать график и записывать путь, и как только мы достигаем места назначения, мы возвращаем путь. Между прочим, я знаю алгоритм Дейкстры, но, пожалуйста, поправьте меня, если я ошибаюсь, мне кажется, что, поскольку у этого графика нет цикла, мы можем использовать обычный bfs для его решения.
Кажется, функция работает нормально. Я хотел бы знать, есть ли какие-нибудь улучшения, которые я могу сделать, чтобы сделать его лучше.
Кстати, мне было трудно придумать сложность времени / пространства для этого алгоритма … Не похоже, что он посещает только одно место один раз.