in Algorithms edited by
5,701 views
21 votes
21 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.7k views

10 Comments

what does PHI mean?
3
3
And between A and E is it undirected or typos?
0
0
guess the image needs to be redrawn. it is 0 and not phi. And direction is from E-A.
7
7
What is O 's significance
0
0
edited by

Answers and analysis based on the image (as drawn on the left side) considered by me  

2
2
85 will be the cost
0
0

85 will be the cost

@Puja Mishra ji Could you please mention the mistake ?

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

32 votes
32 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