CODEWITHSUNDEEP
algorithmtime-complexitydynamic-programmingdijkstra
Sankalp
Sankalp

Reputation: 2824

Shortest Path Algorithms: Dynamic Programming vs Dijkstra's algorithm

Running shortest path algorithm on a Directed Acyclic Graph (DAG) via dynamic programming which uses memoization has a runtime complexity of O(V + E) which can be verified using the following equation:

d(s,v) = min{ d(s,u) + w(u,v) }, over all vertices u->v

Now, Dijkstra's algorithm also requires the graph to be directed. And the algorithm has a runtime complexity of O(E + V.log(V)) using min priority queues and this is clearly slower than the memoized version of DP.

According to wiki:

This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.

Am I missing something here? I am just not able to digest the contradiction here..

Upvotes: 2

Views: 4402

Answers (2)

vmcloud
vmcloud

Reputation: 652

In your dynamic programming, I do not think it is a correct formula, because it is based on the fact that d(s, u) is already the shortest path between s, u. But you can not confirm that. To confirm that you should get the "shortest vertices" step by step using greedy method, so that is what Dijkstra's algorithm do.

And for Dynamic programming, the Floyd–Warshall algorithm is a typical way, you can reference it http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm. Think it carefully!

Upvotes: 2

Amadan
Amadan

Reputation: 198324

Dijkstra's Algorithm is not restricted to DAGs; it can be run on any graphs with no negative path weights, cyclic or otherwise. Topological sorting, that you most likely are referring to, fails the "arbitrary" clause of your Wiki quote.

Upvotes: 3

Related Questions