shortest path vs Dijkstra algorithm
I have implemented the Dijkstra algorithm from the pseudocode found in the reference "Introduction to Algorithms", 3rd edition by Cormen, for the single-source shortest path problem.
My implementation was made on python using linked lists to represent graphs in an adjacency list representation. This means that the list of nodes is a linked list and each node has a linked list to represent the edges of each node. Furthermore, I didn't implement or use any binary heap or fibonacci heap for the minimum priority queue that the algorithm needs, so I search for each node in O(V) time inside the linked list of nodes when the procedure needs to extract the next node with the smallest distance from the source.
On the other hand, the reference also provides an algorithm for DAG's (which I have implemented) using a topological sort before applying the relaxation procedure to all the edges.
With all these context, I have a Dijkstra algorithm with a complexity of
O(V^2)
And a DAG-shortest path algorithm with a complexity of
O(V+E)
By using the timeit.default_timer() function to calculate the running times of the algorithms, I have found that the Dijkstra algorithm is faster that the DAG algorithm when applied to DAGs with positive edge weights and different graph densities, all for 100 and 1000 nodes.
Shouldn't the DAG-shortest path algorithm be faster than Dijkstra for DAGs?
链接地址: http://www.djcxy.com/p/35190.html下一篇: 最短路径vs Dijkstra算法