1

Возник такой вопрос, есть ли какие то более менее быстрые алгоритмы кроме алгоритма Дейкстры по нахождению оптимального пути между нодами графа?

1 ответ 1

1

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

Undirected graphs

Weights    Time complexity          Author
^^^^^^^    ^^^^^^^^^^^^^^^^^        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ℝ+         O(V^2)                   Dijkstra 1959
ℝ+         O((E + V) log V)         Johnson 1977 (binary heap)
ℝ+         O(E + V log V)           Fredman & Tarjan 1984 (Fibonacci heap)
ℕ          O(E)                     Thorup 1999 (requires constant-time multiplication).

PS в той же статье википедии есть подобная таблица для направленных ациклических графов

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки