in Algorithms edited by
5,517 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

30 votes
30 votes
Best answer

$\quad\textbf{DIJKSTRA}{(G,w,s)}$
$\quad 1 \quad \textbf{INITIALIZE-SINGLE-SOURCE}(G,s)$
$\quad 2 \quad S = \emptyset$
$\quad 3\quad Q = G.V$
$\quad 4\quad \textbf{while } Q \neq \emptyset$
$\quad 5\quad \quad u = \textbf{EXTRACT-MIN}(Q)$
$\quad 6\quad \quad S = S \cup \{u\}$
$\quad 7\quad \quad \textbf{for each vertex } v \in G.Adj[u]$
$\quad 8\quad \quad\quad \textbf{RELAX}(u,v,w)$

Correct Solutions:
$(A).$

$Q=\left\{\overset{\boxed{0}}{\text{A}},\overset{\boxed{\infty}}{\text{B}}, \overset{\boxed{\infty}}{\text{C}}, \overset{\boxed{\infty}}{\text{D}}, \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{\infty}}{\text{F}}   \right\}$

  • First we visit $\text{A}$ as it is the one with smallest distance $0$
  • Relax operation updates distances to $\text{B,C,F}$ as $6,90,70$ respectively
    $Q=\left\{\overset{\boxed{6}}{\text{B}}, \overset{\boxed{90}}{\text{C}}, \overset{\boxed{\infty}}{\text{D}}, \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{70}}{\text{F}}   \right\}$
  • $\text{B}$ is next visited as its distance is now $6$
  • Relax operation updates distance to $\text{D}$ as $41+6=47$
    $Q=\left\{ \overset{\boxed{90}}{\text{C}}, \overset{\boxed{47}}{\text{D}}, \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{70}}{\text{F}}   \right\}$
  • $\text{D}$ is next visited as its distance is now $47$
  • Relax operation updates distance to $\text{C}$ as $47+12=59$
    $Q=\left\{ \overset{\boxed{59}}{\text{C}},  \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{70}}{\text{F}}   \right\}$
  • $\text{C}$ is next visited as its distance is now $59$
  • Relax operation updates distance to $\text{F}$ as $59+10=69$
    $Q=\left\{ \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{69}}{\text{F}}   \right\}$
  • $\text{F}$ is next visited as its distance is now $69$
  • Relax operation updates distance to $\text{E}$ as $69+15=84$
    $Q=\left\{\overset{\boxed{84}}{\text{E}}\right\}$
  • Finally $\text{E}$ is visited.

So, the sequence of node visits are $\text{A}, \text{B}, \text{D}, \text{C}, \text{F}, \text{E}$

$(B).$ Sequence of vertices in the shortest path from $\text{A}$ to $\text{E}$: $\text{A}- \text{B}- \text{D}-\text{C}- \text{F}- \text{E}$

$(C).$ Cost of the shortest path from $\text{A}$ to $\text{E} = 84.$

edited by

1 comment

Thanks Sir :)
0
0
13 votes
13 votes
Part a:       A B D C F E

Part b:       A B D C F E

Part c :      84
edited by

4 Comments

Path is A-F-E ... E->A is 2 .... U can easily see it without using Dijkstra ....
0
0
Sorry 84 will be the ans ... path is ABDCFE
0
0
The answer for part (a) must be ABCFDE .

*BECAUSE IT IS ASKED FOR SEQUENCE OF VERTICES VISIITED ON THE GRAPH AND NOT SEQUENCE OF VERTICES SELECTED.

*The sequence of vertices selected for shortest path(ABDCFE) is the answer for part (b) of the question.
0
0
2 votes
2 votes

Here picture is not clear so two points need to be cleared

1.direction E -->A 

2.Phi representes zero "0" here 

2 Comments

moved by

this is the original figure

0
0
Yes 84 is the right answer.
0
0
1 vote
1 vote

Part a and b are clear. Just dry run Dijkstra's algorithm, you'll get ABDCFE for both.


Part c:

A human-friendly way to find shortest paths is not to go from Source to Destination, but to go from Destination to Source, using Greedy algorithm mentally.

  1. Start with E and go backwards. There's only one choice that is F.
    We get FE
     
  2. Now from F we have two choices — choose the edge weight 10, or choose the edge weight 70. We'll be greedy and choose 10.
    We get CFE
     
  3. Similarly from C, choose the edge weight 12.
    We get DCFE
     
  4. From D, choose the edge weight 41.
    We get BDCFE
     
  5. From B, choose the edge weight 6.
    We get ABDCFE

This is the shortest path from A to E.

The total weight of it = $15+10+12+41+6=84$

Related questions