Алгоритм JavaScript: распечатать путь из ориентированного графа при заданной стоимости

Вот проблема, которую можно смоделировать с помощью ориентированного графа с разными затратами на каждом ребре.

Наш вход — это массив ребер.

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 для его решения.

Кажется, функция работает нормально. Я хотел бы знать, есть ли какие-нибудь улучшения, которые я могу сделать, чтобы сделать его лучше.

Кстати, мне было трудно придумать сложность времени / пространства для этого алгоритма … Не похоже, что он посещает только одно место один раз.

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *