Shortest Path Algorithms: Dynamic Programming vs Dijkstra's algorithm

Question

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..

From what I gather the dp algorithm you describe is Bellman Ford which is slower than Dijkstra's but can handle arbitrary graphs with no negative cycles. The runtime is O(VE). Please verify you haven't muddled up your analysis. — ldog
– ldog, Commented Jan 26, 2015 at 6:41
No, the analysis of the DP algorithm is correct if you consider the memoization bit. Since we have only O(E) subproblems, the overall complexity will turn out to be O(E+V). — Sankalp
– Sankalp, Commented Jan 26, 2015 at 6:43
You need to run your algorithm O(V) times in the worst case each with worst case O(E) sub problems hence the runtime of O(VE). Please see the analysis of bellman ford on Wikipedia to see what I mean. — ldog
– ldog, Commented Jan 26, 2015 at 6:46
@ldog: You are barking up the wrong algorithm :D He's talking about Topological sorting, not about Bellman-Ford. — Amadan
– Amadan, Commented Jan 26, 2015 at 6:49

Amadan · Accepted Answer · 2015-01-26 06:24:53Z

3

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.

answered Jan 26, 2015 at 6:24

Amadan

200k23 gold badges253 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Sankalp Over a year ago

Can you please explain what is meant by failing the "arbitrary" clause in case of DP solution?

Amadan Over a year ago

Dijkstra's can solve cyclic graphs. Topological sorting can't. It's like coming across the sentence "Formula 1 are fastest land-based vehicles", then wondering if that's correct because Concorde goes faster. Not land-based, doesn't matter. Same here: Dijkstra's is the fastest if you allow cyclic graphs; the fact that Topological sorting can find shortest path faster doesn't matter because it only does it on DAGs.

Sankalp Over a year ago

Thanks, got the difference!

vmcloud · Accepted Answer · 2015-01-26 07:12:51Z

2

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!

edited Jan 26, 2015 at 7:12

answered Jan 26, 2015 at 6:26

vmcloud

6524 silver badges13 bronze badges

1 Comment

Sankalp Over a year ago

In fact, now as I see it, the DP solution would also return me the shortest paths to all other vertices from a single source vertex in the given time bound only..

Collectives™ on Stack Overflow

Shortest Path Algorithms: Dynamic Programming vs Dijkstra's algorithm

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related