Почему алгоритмы кратчайшего пути всех пар работают с отрицательными весами?
Недавно я изучал алгоритмы кратчайшего пути для всех пар, такие как алгоритм Флойда-Варшалла и Джонсона, и заметил, что эти алгоритмы дают правильные решения, даже если граф содержит отрицательные весовые ребра (но не отрицательные весовые циклы). Для сравнения, алгоритм Дейкстры (кратчайший путь из одного источника) не работает для ребер с отрицательным весом. Что заставляет алгоритмы кратчайшего пути всех пар работать с отрицательными весами?
2 ответа
Алгоритм коротких путей всех пар Флойда Варшалла работает для графов с отрицательным весом ребер, поскольку правильность алгоритма не зависит от неотрицательности веса ребер, в то время как правильность алгоритма Дейкстры основана на этом факте.
Правильность алгоритма Дейкстры:
У нас есть 2 набора вершин на каждом шаге алгоритма. Множество A состоит из вершин, для которых мы вычислили кратчайшие пути. Множество B состоит из оставшихся вершин.
Индуктивная гипотеза: на каждом шаге мы будем предполагать, что все предыдущие итерации верны.
Шаг индукции: Когда мы добавляем вершину V к множеству A и устанавливаем расстояние, равное dist[V], мы должны доказать, что это расстояние является оптимальным. Если это не оптимально, то должен быть какой-то другой путь к вершине V, который имеет меньшую длину.
Предположим, что какой-то другой путь проходит через некоторую вершину X в множестве B.
Теперь, так как dist[V] <= dist[X] поэтому любой другой путь к V будет иметь длину по крайней мере dist[V], если граф не имеет отрицательных длин ребер.
Корректность алгоритма Флойда Варшалла: Любой путь от вершины S до вершины T будет проходить через любую другую вершину U графа. Таким образом, кратчайший путь от S до T может быть вычислен как
min( shorttest_path(от S до U) + shorttest_path(от U до T)) для всех вершин U в графе.
Как вы можете видеть, нет никакой зависимости от ребер графа, чтобы быть неотрицательным, пока вспомогательные вызовы вычисляют пути правильно. И дополнительные вызовы вычисляют пути правильно, пока базовые случаи были правильно инициализированы.
Алгоритм Дейкстры не работает для отрицательного края веса, потому что он основан на жадной стратегии (предположение), что после добавления вершины v в набор S d [v] содержит минимально возможное расстояние.
Но если последняя вершина в Q была добавлена в S и у нее есть некоторые исходящие отрицательные ребра веса. Эффекты на расстоянии, вызванные отрицательными краями, не будут учитываться.
Тем не менее, все пары алгоритмов кратчайших путей будут фиксировать эти обновления.