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

Best answer
37 votes
37 votes

$\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
14 votes
14 votes
Part a:       A B D C F E

Part b:       A B D C F E

Part c :      84
edited by
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 

1 votes
1 votes

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

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