Algorithm:- Multistage graphs

Question

Can someone share some multistage graph where dijkstra will fail but DP works correct?

Comments

@rahul sharma 5

no, what he is applying is not at all dijikstra algorithm,

if you will apply dijikstra algorithm, you will get d_min(V₁, V₁₂) = 16 , which is correct.

---

some people don't consider dijkstra's algo as some greedy approach , they consider it dynamic approach. CLR claims it greedy and i'll go with CLR.

in your video , what he described is basic greedy approach. this approach will support my past argument. # 2+9 is not less than 7+3.

---

In Multistage Graph Dijkstra Algorithm work fine because Dijkstra algorithm finds the shortest path from source to every vertex.

In this example, if I applied Dijkstra Algorithm 

Solution looks like

Shortest Path from A to F: A---->B------->E-------->F

Minimum Cost from A to F = 6

But in Greedy Method:

A---------->B---------->D------------>F

Minimum cost Using Simple Greedy Method = 7

---->Time Complexity Using Dynamic Programming is O(E)

---->Dijkstra Algorithm is also Greedy Algorithm for Finding Single Source Shortest Path Problem. It Takes

O(E log V) time, it is more than O(E).

---->Greedy Method always choose minimum cost of the vertex. So, sometimes it failed to find the right answer.

 

 

Answer 1

Dijkstra Algorithm will fail only if there is NEGATIVE WEIGHT EDGE CYCLE .  We use dynamic programming in Multi Stage graph because of the time complexity O(E) rather than  Dijkstra: O(ElogV)  and moreover if we apply greedy approach at every vertex for example there is graph of 4 vertices.

Firstly there is negative edge from u->w but it does not form any cycle.Dijsktra will also give correct answer. And let us say we want to find the shortest distance from S -> W . What greedy approach says is find optimal solution LOCALLY.  

1) s -> v   (Because we chose minimum of (  s->u , s->v ) and minimum distance = 1

2) v -> w ( Because only path leading to w , so no option)  and minimum distance = 1 + 1 =  2

But if we apply Dynamic approach , it will explore all the edges and you can clearly see S->U->W is the least cost path of = 3 - 2 = 1. 

Note: Now one must be in doubt then is Dijkstra greedy or dynamic . You can read Wikipedia article :

1)  https://www.quora.com/Is-Dijkstras-Algorithm-a-greedy-algorithm-or-a-dynamic-programming-algorithm#

2)  https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic_programming_perspective

3) https://stackoverflow.com/questions/14038011/dijkstras-algorithm-a-greedy-or-dynamic-programming-algorithm

Comments

It's greedy because you always mark the closest vertex. It's dynamic because distances are updated using previously calculated values.

---

If We applied Dijkstra Algorithm 

This is the Solution

Here S---->U----------->W

Minimum Cost = 1 

----->Time Complexity Using Dynamic Programming is O(E)

---->Dijkstra Algorithm is also Greedy Algorithm for Finding Single Source Shortest Path Problem. It Takes

O(E log V) time, it is more than O(E).

---->Greedy Method always choose minimum cost of the vertex. So, sometimes it failed to find the right answer.

---

Dijkstra Algorithm will fail only if there is NEGATIVE WEIGHT EDGE CYCLE.

This is wrong.

Djikstra fails even in case of negative edge. It may work correct sometimes, but other times it can fail. Therefore Djikstra is not used in graphs with negative edges.

---

 @ gmrishikumar An algorithm will be correct for a problem if it gives correct result for all of it’s test cases in the given range of values. So there nothing like it may work sometimes. Either it will work or it will fail.