Алгоритм SSSP: минимальное расстояние, но при определенном количестве «прыжков» - PullRequest
Новая
       15

Алгоритм SSSP: минимальное расстояние, но при определенном количестве «прыжков»

1 голос
/ 29 марта 2019

Учитывая направленный взвешенный граф (без отрицательных ребер), каково самое короткое расстояние от одного узла до другого, которое также удовлетворяет условию, что число «прыжков» от одного узла / вершин к другому должно быть меньше, чемопределенное значение к.(Где k определенно меньше, чем количество узлов).

Один "прыжок" определен для перемещения от одного узла к другому, и значение "прыжка" начинается с 1 от исходного узла.

Проблема не так проста, как простой запуск алгоритма Дейкстры, так как этот алгоритм дает вам только кратчайшее расстояние без учета количества «прыжков».

Замечание 1: кратчайший путь от исходного к конечному узлу может превышать максимально допустимое количество «прыжков».

Примечание 2: расширение алгоритма Дейкстры для минимизации количества «прыжков» приведет кдать вам возможный ответ, но он может быть не самым коротким.

Обратите внимание, что приоритет по-прежнему заключается в том, чтобы минимизировать кратчайшее расстояние, просто существует новое условие количества «прыжков», которое должно быть меньшечем определенное значение.

1 Ответ

0 голосов
/ 01 апреля 2019

Существует решение, которое модифицирует алгоритм Беллмана-Форда для вашего конкретного случая.На классическом Bellman-Ford (https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) вы должны выполнить N-итераций.

Идея решения заключается в следующем:

Установить расстояние [корень] = 0,и расстояние [x] = бесконечность для каждого другого узла.

Теперь мы пройдемся по всем ребрам один раз и попытаемся улучшить наш ответ. 

For Edge in Edges:
    distance[Edge.dest] = min( distance[Edge.dest], distance[Edge.src] + Edge.cost)

Применение этого шага один раз даст намкратчайший путь от источника, который использует не более одного ребра.Теперь идея повторить этот шаг ровно K раз.Это даст нам точно кратчайший путь от начала координат до каждого другого узла, используя не более K ребер.

Сложность: O (K * | ребер |)

...