Время выполнения алгоритма Дейкстры в приоритетной очереди, реализованной отсортированным списком / массивом

Question

Так что мне любопытно узнать, какое время работы алгоритма включено в приоритетной очереди, реализованной отсортированным списком / массивом. Я знаю, что для несортированного списка / массива это O ((n ^ 2 + m)), где n - количество вершин, а m - количество ребер. Таким образом, это равняется O (n ^ 2) времени. Но было бы быстрее, если бы я использовал отсортированный список / массив ... Каково было бы время выполнения? Я знаю, что extramin будет постоянным временем.

Answer 1

Хорошо, давайте рассмотрим, что нам нужно для алгоритма Дейкстры (для дальнейшего использования, как правило, вершины и ребра используются как V и E, например O (VlogE)):
Объединение всех отсортированных списков смежности: O (E)
Минимальный экстракт: O (1)
Ключ уменьшения: O (V)
Дейкстра использует O (V) для извлечения минимальных операций, а O (E) уменьшает ключевые операции, поэтому:
O (1) * O (V) = O (V)
O (E) * O (V) = O (EV) = O (V ^ 2)
Взяв наиболее асимптотически значимую часть:
Возможное асимптотическое время выполнения O (V ^ 2).
Можно ли это сделать лучше? Да. Посмотрите на двоичные кучи и лучшие реализации очередей с приоритетами.

Редактировать : Я действительно допустил ошибку, теперь, когда я смотрю на нее снова. E не может быть выше V ^ 2 или, другими словами, E = O (V ^ 2).
Следовательно, в худшем случае алгоритм, который мы заключили, работает в O (EV) на самом деле O (V ^ 2 * V) == O (V ^ 3)

Answer 2

Я использую SortedList http://blog.devarchive.net/2013/03/fast-dijkstras-algorithm-inside-ms-sql.html Это примерно в 20-50 раз быстрее, чем сортировка списка один раз за итерацию