Я пытаюсь узнать об алгоритме Беллмана-Форда, но я застрял с доказательством правильности. Я использовал Википедию, но просто не могу понять доказательство . Я не нашел ничего полезного на Youtube. Надеюсь, кто-нибудь из вас сможет объяснить это кратко. Эта страница "Правильность Bellman-ford, можем ли мы сделать лучше" не отвечает на мой вопрос.
Спасибо.
Давайте посмотрим на проблему с точки зрения динамического программирования графа без отрицательного цикла.
Мы можем визуализировать таблицу запоминания динамического программирования следующим образом:
Столбцы представляют узлы, а строки представляют шаги обновления (узел 0 — это исходный узел), а стрелки, направляющие от одного поля на шаге к другому на следующем шаге, — это обновления min (шаг 0 — это инициализация).
Мы выбираем один путь из всех кратчайших путей и показываем, почему он правильный. Выберем 0 -> 3 -> 2 -> 4 -> 5. Это кратчайший путь от 0 до 5, иначе можно выбрать любой другой. Мы можем доказать правильность редукцией. Начальным является исходный 0, и очевидно, что расстояние между 0 и самим собой должно быть 0, кратчайшим. И мы предполагаем, что 0 -> 3 -> 2 является кратчайшим путем между 0 и 2, и мы собираемся доказать, что 0 -> 3 -> 2 -> 4 является кратчайшим путем между 0 и 4 после третьей итерации.
Сначала докажем, что после третьей итерации узел 4 необходимо зафиксировать/подтянуть. Если узел 4 не фиксирован, это означает, что существует по крайней мере один путь, отличный от 0 -> 3 -> 2 -> 4, который может достигать 4, и этот путь должен быть короче, чем 0 -> 3 -> 2 -> 4, что противоречит нашему предположению, что 0 -> 3 -> 2 -> 4 -> 5 является кратчайшим путем между 0 и 5. Тогда после третьей итерации 2 и 4 должны быть соединены.
Во-вторых, мы доказываем, что эта релаксация должна быть кратчайшей. Он не может быть больше или меньше, потому что это единственный кратчайший путь.
Давайте посмотрим на график с отрицательным циклом.
А вот его таблица запоминания:
Докажем, что на итерации |V| здесь |V| количество вершин 6, обновление не должно останавливаться.
Будем считать, что обновление остановилось(и идет отрицательный цикл). Давайте посмотрим цикл 3 -> 2 -> 4 -> 5 -> 3.
dist(2) ‹= dist(3) + w(3, 2)
dist(4) ‹= dist(2) + w(2, 4)
dist(5) ‹= dist( 4) + w(4, 5)
dist(3) ‹= dist(5) + w(5, 3)
И мы можем получить следующее неравенство из приведенных выше четырех неравенств, суммируя левую и правую части:
dist(2) + dist(4) + dist(5) + dist(3) ‹= dist(3) + dist(2) + dist(4) + dist(5) + w(3, 2) + w( 2, 4) + ш(4, 5) + ш(5, 3)
Вычитаем расстояния с обеих сторон и получаем, что:
w(3, 2) + w(2, 4) + w(4, 5) + w(5, 3) ›= 0, что противоречит нашему утверждению что 3 -> 2 -> 4 -> 5 -> 3 является отрицательным циклом.
Итак, мы уверены, что на шаге |V| и после этого шага обновление никогда не остановится.
Мой код находится здесь, в Gist.
Ссылка:
