DAG-shortest path vs Dijkstra algorithm

2
votes

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?

1
graphdijkstrashortest-pathdirected-acyclic-graphs
Is the dijk algo faster for ALL graph densities? or just some of them? - NL628
It was faster for all my test cases - JsMartinez

1 Answers

1
votes

Your running time analysis for both algorithms is correct and it's true that DAG shortest path algorithm is faster than Dijkstra's algorithm for DAGs.

However, there are 3 possible reasons for your testing results:

  1. The graph you used for testing is very dense. When the graph is very dense, E ≈ V^2, so the running time for both algorithms approach O(V^2).

  2. The number of vertices is still not large enough. To solve this, you can use a much larger graph for further testing.

  3. The initialization of the DAG costs a lot of running time.

Anyway, DAG shortest path algorithm should be faster than Dijkstra's algorithm theoretically.