Final Analysis DIJIKSTRA ALGORITHM

Question

Acc. to dijkstra's algorithm:
What will be the shortest path from A to B ?

1) When the edge of length 15 is present.
2) when the edge of length 15 is removed.

Answer 1

if path of 15 is there

then it will be considered as shortest path..dikjstra algo wont update it..updation takes place only when distance is less than current distance

coming to second que

if path of 15 is not there

then  path 2-13 choosen or 2-10-3 will be choosen...

say 2-13 edge vertices are labelled as CD

and on 2-10-3 vertices are labelled as EF

(assuming alphabetic order while processing ie removind C first from priority,2-13 path will choosen)

Comments

Only 2-13 will be choosen.

We cannot choose 2-10-3

When you have explored 2-10 ,then cost is 12.But other 2 is also explored and it will be processed before 12 cost and it will change B to 15.

---

@rahul,

yes you are absolutely coorect,

 if edge 15 is not present, dijikstra will always select 2-13 as path, it will never select 2-10-3 as path

Answer 2

Final Answer

A) 15
B) 2 10 13

Comments

DIJIKSTRA ALGORITHM

is based on Greedy Strategy 
When Edge 15 is there

From A ,it greedily select the strict shortest path  ie  2
From 2 there is no other path than 10 similarly 3

When Edge 15 is NOT there

path reported by Dijikstra will be same .

Note
If we remove edge 15 the graph will turn out to be multistage graph. And greedy algorithm is not guaranteed to produce shortest path in Multistage Graph .
We need to apply Dynamic Programming Strategy to get the shortest path [ in the given graph DP can report any path since all paths have cost 15. However the path reported By DP is affected by how we implement DP strategy by Forward or Backward approach 
 

---

@Pc can you please tell me that after removal of 15, why it becomes multi stage graph.I am not aware of multistage graph.Even if we remove 15,then also dijakstra gives correct answer as it has positive weights and connected.Please clearify

Answer 3

Here all paths from A to B are of 15 weight.  But when dijkshtra's algo run,

it should give path  A --- B (direct edge).

---

Why only this path ?

Ans:  when we run dijikshtra, taking A as source, in first iteration we are able

         to reach B(but we are not selecting this in 1st Iteration, just updating the

        distance to B) i.e. a direct edge from A to B.

          so, it will only be updated when we get some shorter path, but it is not the case.

Comments

i thought , you directly took 15 (a--b) , thats why i asked , how directly 15 , its greedy.

---

Ok, now u get it.. :)

---

yes, 15 is not chosen immediately. Algorithm follows greedy choice. In step 1 with A as source distance to B is updated as 15. Now, greedy choice continues and we traverse all other source vertices. Eventually greedy choice leads to B- but till here the distance from A-B won't be changed.

Answer 4

I got 15 as the shortest path.