Проблема кратчайших путей с двумя условиями

Question

Скажем, у меня есть ориентированный граф G (V, E, w, c), где w - положительный вес каждого ребра, а c - стоимость каждого ребра, равная 1 или 0. Мне нужно найти алгоритм, который для заданной исходной вершины u находит кратчайшие пути от u до каждой вершины из V, имеющие стоимость ≤ k (где k≥1).

Я пытался изменить алгоритм Беллмана Форда, но, похоже, не могу найти решение.

Answer 1

Позвольте мне переформулировать мое понимание проблемы.

Для всех вершин, которые вы можете достичь с ценой не более чем k, вам нужен путь минимального веса, который проходит от вершины u.

Вам нужна комбинация идей, чтобы добраться туда.

Предположим, что объект RouteToNode имеет следующие атрибуты: cost, weight, node, lastRouteToNode и автоинкремент id. Это связанный список, возвращающий нас к исходному узлу и позволяющий реконструировать маршрут. Мы сравниваем их по cost, затем weight, затем id.

У нас есть хэш / словарь / как хотите, чтобы он назывался, который отображает узлы с наименьшим весом RouteToNode объекта, достигающего этого узла. Назовите это bestRoute.

У нас есть список todo, в котором есть RouteToNode s, которые мы еще не обработали, и который является приоритетной очередью, которая всегда возвращает минимальное значение RouteToNode. Обратите внимание, что он всегда возвращает их от самой низкой стоимости до самой высокой.

Мы начинаем с bestRoute, в котором ничего нет, и с todo очередью только с одним RouteToNode, а именно:

{
    id: 0,
    cost: 0,
    weight: 0,
    node: u,
    lastRouteToNode: null
}

И теперь мы выполняем следующий псевдокод:

while todo is not empty:
    thisRouteToNode = todo.pop()
    if thisRouteToNode.node not in bestRoute or
      thisRouteToNode.weight < bestRoute[thisRouteToNode.node].weight:
        bestRoute[thisRouteToNode.node] = thisRouteToNode
        for edge adjacent to thisRouteToNode.node:
            construct nextRouteToNode by adding edge
            if nextRouteToNode.cost <= k:
                todo.push(nextRouteToNode)