4446
правок
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Поиск кратчайших путей в планарных графах с весами дуг общ…») |
Irina (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
На графах общего вида лучший известный алгоритм – алгоритм Беллмана-Форда – выполняется за время O(mn), где n и m – число вершин и ребер, соответственно. Алгоритмы на графах, не имеющих ребер с отрицательными весами, выполняются намного быстрее. К примеру, алгоритм Дейкстры в реализации с фибоначчиевой кучей требует O(m + n log n) времени, а в случае с целочисленными весами алгоритм Торупа выполняется за линейное время. Голдберг [5] также представил алгоритм с временем выполнения O(m | На графах общего вида лучший известный алгоритм – алгоритм Беллмана-Форда – выполняется за время O(mn), где n и m – число вершин и ребер, соответственно. Алгоритмы на графах, не имеющих ребер с отрицательными весами, выполняются намного быстрее. К примеру, алгоритм Дейкстры в реализации с фибоначчиевой кучей требует O(m + n log n) времени, а в случае с целочисленными весами алгоритм Торупа выполняется за линейное время. Голдберг [5] также представил алгоритм с временем выполнения <math>O(m \sqrt{n} \; log \; L)</math>, где L – абсолютная величина наибольших отрицательных весов ребер. Заметим, что его алгоритм является слабо полиномиальным. | ||
== Нотация == | == Нотация == |
правок