Алгоритм Беллмана

Контенус

Алгоритм Беллмана основан на следующем наблюдении: если нам известны все значения дуг (u, v) с u в подграфе и v вне этого подграфа. Если мы знаем все кратчайшие пути к u, то можем вычислить d(v) = min{d(u) + weight(u,v)}. Алгоритм Беллмана представляет собой алгоритм из динамическое программирование жадный (похож на первый поиск хлеба), он посещает все возможные решения.

Условия.

нет цикла
Только лук
Конечное количество вершин
Источник (и, кстати, цель), определенный

Алгоритм Беллмана принимает на вход график ориентированные, взвешенные по положительным действительным числам и исходной вершине. Это включает в себя постепенное построение подграфа, в котором различные вершины классифицируются в порядке возрастания их минимального расстояния от начальной вершины. Расстояние соответствует сумме весов взятых дуг.

Первоначально считаем, что расстояния от каждой вершины до начальной вершины бесконечны, за исключением начальной вершины, для которой расстояние равно 0. Начальным подграфом является пустое множество.

На каждой итерации мы выбираем вне подграфа такую вершину, что все ее потомки находятся в подграфе, и добавляем ее в подграф. Затем мы обновляем расстояния соседних вершин добавленной. Обновление работает следующим образом: новое расстояние от соседней вершины является минимальным между существующее расстояние и полученный добавлением вес дуги между соседней вершиной и вершиной, прибавленный к расстоянию от добавленной вершины.

Мы продолжаем таким образом, пока вершины не будут исчерпаны (или пока не будет выбрана целевая вершина).

Алгоритм Беллмана с одним источником кратчайшего пути DAG

По практическим причинам решение алгоритма Беллмана возвращает только вектор, содержащий посещенную вершину, список предшественников (уже проверенных вершин) и значения кратчайших путей ко всем остальным обновленным вершинам. Что соответствует текущей строке представленной таблицы.

Оптимальность

Вершина считается проверенной, если все ее предшественники проверены. То есть мы знаем, кратчайший путь из всех своих предшественников. В начальном состоянии мы подтвердили исходную точку и знаем пути размера 1, начинающиеся из исходной точки. Следовательно, следующая вершина, подлежащая проверке, имеет путь только с проверенными вершинами. По индукции мы делаем вывод, что мы проверили кратчайший путь от начала координат до этой вершины.

Д[0] = 0;      
за каждая вершина i ‚ 0 делает C[i] = 0; D[i] = L[1, i];   
за k = 1 год - 1 сделать  
    за каждый я преемник k делать  
        если (D[k] + L[k, i] < D[i]), то D[i] = D[k] + L[k, i]; С [я] = к;            
        конец      
    конец     
конец
Подбросить Д