Первая страница / Визуализаторы / Графы. Потоки и паросочетания /

Максимальный поток минимальной стоимости

Голосование: 11, 8

Запустить визуализатор

Автор визуализатора: Алексей Сергушичев

Описание алгоритма


artem / 2009-12-20 17:20:18

Непонятно, как и из чего считается стоимость пропущенного максимального доп. потока, почему в примере 2 она равна 18.

Плохие пояснения.

artem / 2009-12-20 20:31:57

И вообще остается загадкой, что просиходит на шаге 6, когда с помощью алгоритма Дейкстры непонятно откуда появляется расстояние = "2" в вершинах 2,3 и "5" в вершине t.

КАК?! При том, что первый раз алгоритм Дейктры работает правильно (на шаге 2).

RPG / 2011-05-17 11:21:20

Алгоритм работает правильно, просто он объяснен [...] . Здесь используется не обычный алгоритм Дейкстры, а алгоритм Дейкстры с потенциалами. Описание ему найти в сети довольно затруднительно.

Abert / 2016-01-03 22:51:15

Неправильный алгоритм. Неправильно находятся пути и, соответственно, потенциалы. В Дейкстре с потенциалами мы находим кратчайшие пути по новым ребрам, затем, чтобы узнать путь по изначальным ребрам(которые могут быть отрицательными) мы прибавлям к каждой стомости пути от старта до другой вершины ее потенциал. В данном алгоритме этого прибавления нет

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий