Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями

На графах общего вида лучший известный алгоритм – алгоритм Беллмана-Форда – выполняется за время O(mn), где n и m – число вершин и ребер, соответственно. Алгоритмы на графах, не имеющих ребер с отрицательными весами, выполняются намного быстрее. К примеру, алгоритм Дейкстры в реализации с фибоначчиевой кучей требует O(m + n log n) времени, а в случае с целочисленными весами алгоритм Торупа выполняется за линейное время. Голдберг [5] также представил алгоритм с временем выполнения O(m p n log L), где L – абсолютная величина наибольших отрицательных весов ребер. Заметим, что его алгоритм является слабо полиномиальным.