Как в худшем случае запустить Bellman-Ford?

Я пытаюсь сделать оптимизированную версию алгоритма Bellman Ford для работы в худшем случае. Оптимизированная версия Я имею в виду, что если после ослабления 1 раунда ребер нет дальнейшего обновления на кратчайшем расстоянии, он завершается.

Например, простой связный взвешенный ориентированный граф с 7 вершинами, такой, что при запуске оптимизированного алгоритма Беллмана-Форда из исходной вершины 0 требуется не менее 5 раундов для получения правильных кратчайших путей.

График не может содержать цикл с отрицательным весом. т.е. обрабатываются все исходящие ребра из вершины 0, затем ребра из вершины 1 и т. д.

Я знаю, что это связано с циклами. Но я не очень уверен, что стратегия построения графика соответствует требованиям.


algorithm bellman-ford
person Milk_QD    schedule 31.10.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Для вашей версии алгоритма Беллмана-Форда потребуется столько итераций, сколько наибольшая длина (в ребрах) всех кратчайших путей в графе.

Рассмотрим ориентированный граф с n вершинами. Вы добавляете к графу ребра 1 -> 2 -> 3 -> ... -> n, каждое из которых имеет небольшой положительный вес. Затем вы можете добавить столько произвольных тяжелых кромок, сколько захотите. Понятно, что кратчайший путь от 1 до n имеет длину n-1. Таким образом, вашему алгоритму потребуется ровно n-1 итераций.

Далее следует отметить, что существует улучшенная версия алгоритма Беллмана-Форда. Это называется алгоритм кратчайшего пути и быстрее. Хотя его время выполнения в наихудшем случае равно O(|V|*|E|), что такое же, как у Беллмана-Форда, очень мало графиков может заставить алгоритм достичь этого времени. На практике вы можете рассчитывать на среднее время выполнения O(|E|) (не доказано).

person KonaeAkira    schedule 01.05.2020