GATE CSE 1996 | Question: 17

Question

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

Comments

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

Answer 1

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

Comments

Thanks Sir :)

---

Amazing answer best way to do revision while solving gate question and see the explanation of answer it really brush up the concepts.

Answer 2

Part a:       A B D C F E

Part b:       A B D C F E

Part c :      84

Comments

Logic ? How are you interpreting phi ?

---

u get it now , rt ?

---

graph will be

---

Instead of adding A-C-(90) isn't   A-B-D-C(59) a feasible choice?

---

but in the question 9Φ is written instead of 90. How you are writing 90?

---

@srestha

(a-C) doesnt come in the sequence

---

why not?

---

@srestha

the sequence is ABDCFE if u apply dijikstras which gives value of 84 totally

but urs gives 149

---

Cost will be 85 ...

---

@puja ....how ?

whats the path

---

Path is A-F-E ... E->A is 2 .... U can easily see it without using Dijkstra ....

---

Sorry 84 will be the ans ... path is ABDCFE

---

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.

Answer 3

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

1.direction E -->A 

2.Phi representes zero "0" here 

Comments

this is the original figure

---

Yes 84 is the right answer.

Answer 4

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$