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

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

Реализация

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

Теперь в новом графе находятся расстояния от нужной вершины до остальных. Расстояние в новом графе от a до b d(a, b)=W(a, x)+W(x, y)+…+W(z, b), где x, y…z — промежуточные вершины в кратчайшем пути. Подставляя формулу новых весов, получим d(a, b)=w(a, x)+px-pa+w(x, y)+py-px…+w(z, b)+pb-pz=pb-pa+w(a, x)+w(x, y)+…+w(z, b). Отсюда видно, что длины путей между заданной парой вершин в начальном и новом графах отличаются на константу, следовательно, кратчайший путь в новом графе совпадает с кратчайшим путем в старом графе. Соответственно, длина кратчайшего пути в оригинальном графе равна d(a, b)-pb+pa.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home