Алгоритм Дейкстры с потенциалами

Алгоритм Дейкстры с потенциалами — обобщение алгоритма Дейкстры на случай графов с ребрами отрицательного веса.

Реализация

Каждой вершине i присваивается потенциал p_i. Затем веса ребер переопределяются: для каждого ребра (i, j) новый вес W_{(i, j)}=w_{(i, j)}+p_j-p_i. Потенциалы определяются так, чтобы новые веса были неотрицательными (в графе без контуров отрицательного веса это всегда можно сделать).

Теперь в новом графе находятся расстояния от нужной вершины до остальных. Расстояние в новом графе от a до b d_{(a, b)}=W_{(a, x)}+W_{(x, y)}+…+W_{(z, b)}, где x, y…z — промежуточные вершины в кратчайшем пути. Подставляя формулу новых весов, получим d_{(a, b)}=w_{(a, x)}+p_x-p_a+w_{(x, y)}+p_y-p_x…+w_{(z, b)}+p_b-p_z=p_b-p_a+w_{(a, x)}+w_{(x, y)}+…+w_{(z, b)}. Отсюда видно, что длины путей между заданной парой вершин в начальном и новом графах отличаются на константу, следовательно, кратчайший путь в новом графе совпадает с кратчайшим путем в старом графе. Соответственно, длина кратчайшего пути в оригинальном графе равна d_{(a, b)}-p_b+p_a.