Возник такой вопрос, есть ли какие то более менее быстрые алгоритмы кроме алгоритма Дейкстры по нахождению оптимального пути между нодами графа?
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 в той же статье википедии есть подобная таблица для направленных ациклических графов