Ace Test Series: Algorithms - Graph Algorithms

Question

Answer is given as (B). But, shouldn't it relax point 'c' via 'a' .. So, i guess answer should be D. Is it?

Comments

I think answer must be option d ( may be they have given wrong )

---

Yes , you are right.
Answer is D.

Answer 1

ans is D) a-c-f-g

vertex  parent

a            NULL

b           a

c           a

d          b

e          c

f          c

g         f

Answer 2

B should be answer as source is given as a  and as Dijkastra algorithm we will pick b

Answer 3

Correct me if wrong.

Answer 4

Dijikstra's algorithm should have traverse minimum weight of path. So we can derive like below from above graph through given optional,

(a){a,d,c,f,g} ={6(initial weight) + 2 + 3 + 1} = 12

(b){a,b,d,c,f,g} = {3(initial weight) + 2 + 2 + 3 + 1} = 11

(c){a,c,g} = {5(initial weight) + 7} = 12

(d){a,c,f,g} = {5(initial weight) + 3 + 1} =9

 So answer is B.

Note:  if same weight available in a graph ,at that time we shall take minimum value of initial node will take as followed by next node to destination.