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

its greedy approach then it will take 15, directly ??

---

Sonam , I think u want to ask which edge will be selected at first..

So, edge labelled 2 will be selected first..

But final Answer for path from A to B remain 15( edge from A to B).

---

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.

Answer 5

you have to give the information when there is a tie then which path do we take , old path remains or new path taken .

in case of old path remains then ans will be direct A to B (15 )

and if new path then  i think A => 2 => 13 =>  B or A => 6 => 7 => 2  => B

Comments

its greedy approach then it will take 15, directly ??

---

it depends upon implementation , there is a tie then we take the old path then ans will be direct 15 .

---

dijkstra has multiple implementations?
 

standard?

---

Sir are you sure we have to take some ties and all??

I think we just have strictly greater condition so one who first update the destination vertex will not change its value until and unless wh have shorter path than it?

Answer 6

The Ans is 15 Obviously (all distances are same).

But What will be the path ..... ??

See Using Initialize_single_source algo you will give source as 0 and others as infinity.

Now Run dijsktra Algo all vertices will be updates with the weights so B will be updated 15 irrrespective there are 2 ,6, and 5 path there are being changed to intermediates vertices

 And ultimately when you reach B from others path

you follow

 

d[v]>  d[u]+ w(u,v) (condition is strictly increasing)

 

but since d[v]=15 from A--->B edge so no other path was able to change it(due to strictly increasing path)