Разработать алгоритм для задачи с кратчайшим путем из одного источника, которая выполняется за время O (k (| V | + | E |))

Question

Предположим, нам дан ориентированный граф G = (V, E) с потенциально положительными и отрицательными длинами ребер, но без отрицательных циклов. Пусть s ∈ V будет заданным источником вершина. Как разработать алгоритм для задачи кратчайшего пути из одного источника, которая выполняется во времени O(k(|V | + |E|)), если кратчайшие пути из s в любую другую вершину занимают самое большее k edges?

Answer 1

Вот подход O (k (| V | + | E |)):

1. Мы можем использовать алгоритм Беллмана-Форда с некоторыми модификациями
2. Создать массив D [] для хранения кратчайшего пути от узла s к некоторому узлу u
3. изначально D [s] = 0, а все остальные D [i] = + oo (бесконечность)
4. Теперь после итерации всех ребер k раз и ослабления их, D [u] содержит кратчайшее значение пути от узла s до u после <= k ребер </li>

5. Поскольку любой кратчайший путь s-u имеет не более k ребер, мы можем завершить алгоритм после k итераций по ребрам

   псевдокод:

   для каждой вершины v в вершинах:
   D [v]: = + oo

   D [s] = 0

   повторить k раз:
   для каждого ребра (u, v) с весом w в ребрах:
   если D [u] + w D [v] = D [u] + w