Register

GO Classes DPP | Algorithm |Dijkstra’s algo

451 views
3 3 votes

Consider the following weighted, directed graph. If Dijkstra's single-source shortest path algorithm is run with source vertex 'S', what is the order in which the vertices are finalised (i.e., extracted from the priority queue)?

  • S to A: weight 5
     
  • S to B: weight 2
     
  • B to A: weight 2
     
  • B to C: weight 4
     
  • A to C: weight 1
     
  • A to D: weight 6
     
  • C to D: weight 3

     
  1. $S, B, A, C, D$
     
  2. $S, A, B, C, D$
     
  3. $S, B, C, A, D$
     
  4. $S, B, A, D, C$

3 Answers

Voting & Accepting an answer helps improve the community
← Previous · GO Classes DPP | Alg...Next → · GO Classes DPP | Alg...
← Previous in category · GO Classes DPP | Alg...Next in category → · GO Classes DPP | Alg...
Position:
Show:

Related questions

3 3 votes
3 3 answers
588
588 views
GO Classes asked Sep 13, 2025
588 views
GO Classes DPP | Algorithm |Huffman coding
A file contains the following characters with the given frequencies:a: $45$b: $13$c: $12$d: $16$e: $9$f: $5$What is the total number of bits required to encode the messag...
2 2 votes
2 2 answers
388
388 views
GO Classes asked Sep 13, 2025
388 views
GO Classes DPP | Algorithm |Minimum spanning tree
Consider a connected, undirected graph $G=(V, E)$ with a weight function $w: E \rightarrow \mathbb{R}^{+}$ where all edge weights are distinct. Let $T$ be the Minimum Spa...
3 3 votes
3 3 answers
470
470 views
GO Classes asked Sep 13, 2025
470 views
GO Classes DPP | Algorithm |Recurrence relation
Consider the following recurrence:$$\begin{aligned}& T(n)=2 T(\sqrt{n})+1 \\& T(1)=1\end{aligned}$$Which of the following is NOT true?$T(n)=O(\log \log n)$ $T(n)=O(\log n...
3 3 votes
2 2 answers
361
361 views
GO Classes asked Sep 13, 2025
361 views
GO Classes DPP | Algorithm |ISRO
The recurrence relation that arises in relation with the complexity of binary search is$T(n)=2 T(n / 2)+k$, where k is constant $T(n)=T(n / 2)+k$, where k is constant $T(...