5,525 views

Let $G$ be the directed, weighted graph shown in below figure

We are interested in the shortest paths from $A$.

1. Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node $A$

2. Write down sequence of vertices in the shortest path from $A$ to $E$

3. What is the cost of the shortest path from $A$ to $E$?

Path is A-F-E ... E->A is 2 ....
Answer should be 84. @puja mishra ma'am
u r right ... i hav nt noticed that path ... #sloppy :O

 $A$ $B$ $C$ $D$ $E$ $F$ $0$ $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $A(B,C,F)$ $\times$ $6(A)$ $90(A)$ $\infty$ $\infty$ $70(A)$ $B(D)$ $\times$ $\times$ $90(A)$ $47(B)$ $\infty$ $70(A)$ $D(C)$ $\times$ $\times$ $59(D)$ $\times$ $\infty$ $70(A)$ $C(F)$ $\times$ $\times$ $\times$ $\times$ $\infty$ $69(C)$ $F(E)$ $\times$ $\times$ $\times$ $\times$ $84(F)$ $\times$ $E(A,B,C,D)$ $\times$ $\times$ $\times$ $\times$ $\times$ $\times$

$a)$ $A\rightarrow B\rightarrow D\rightarrow C\rightarrow F\rightarrow E$

$b)$ $A\overset{6}{\rightarrow}B\overset{41}{\rightarrow}D\overset{18}{\rightarrow}C\overset{10}{\rightarrow}F\overset{15}{\rightarrow}E$

$c)$ $A\rightarrow E=84$

(A) A−B−D−C−F−E

(B) A−B−D−C−F−E

(C) 84

by

The cost is 84.