retagged by
7,440 views
25 votes
25 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$?

retagged by

7 Answers

1 votes
1 votes

 

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

0 votes
0 votes

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

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

(C) 84

 

Related questions

26 votes
26 votes
1 answer
2
Kathleen asked Oct 9, 2014
5,107 views
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the ...