in Algorithms edited by
5,525 views
20 votes
20 votes

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$?

in Algorithms edited by
5.5k views

4 Comments

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

7 Answers

1 vote
1 vote

 

  $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$

edited by
0 votes
0 votes

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

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

(C) 84

 
by
0 votes
0 votes

The cost is 84.

Related questions