Я реализовал алгоритм Дейкстры из псевдокода, найденного в справочнике «Введение в алгоритмы», 3-е издание Кормена, для задачи поиска кратчайшего пути с одним источником.
Моя реализация была сделана на python с использованием связанных списков для представления графиков в виде списка смежности. Это означает, что список узлов представляет собой связанный список, и каждый узел имеет связанный список, представляющий края каждого узла. Кроме того, я не реализовал и не использовал какую-либо двоичную кучу или кучу Фибоначчи для очереди с минимальным приоритетом, которая требуется алгоритму, поэтому я ищу каждый узел за время O (V) внутри связанного списка узлов, когда процедура должна извлечь следующий узел с наименьшим удалением от источника.
С другой стороны, в справочнике также представлен алгоритм для DAG (который я реализовал) с использованием топологической сортировки перед применением процедуры релаксации ко всем ребрам.
Со всем этим контекстом у меня есть алгоритм Дейкстры со сложностью
O(V^2)
И алгоритм кратчайшего пути DAG со сложностью
O(V+E)
Используя функцию timeit.default_timer() для расчета времени работы алгоритмов, я обнаружил, что алгоритм Дейкстры быстрее, чем алгоритм DAG, при применении к DAG с положительными весами ребер и различной плотностью графов, все для 100 и 1000 узлов.
Разве алгоритм кратчайшего пути DAG не должен быть быстрее, чем алгоритм Дейкстры для DAG?
