Register

GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm

169 views
3 3 votes

Consider the following code executed while processing vertex $v$:

for each edge e in G.adj(v):

    w = e.to()

    if dist[w] > dist[v] + e.weight():

        dist[w] = dist[v] + e.weight()

        pred[w] = e

        pq.insert(dist[w], w)

Which operation does this code perform?

  1. Processes a vertex for Prim's algorithm
     
  2. Computes the MST of a weighted graph
     
  3. Topologically sorts a directed graph
     
  4. Processes a vertex for Dijkstra's algorithm
     
  5. Detects a cycle in a graph

1 Answer

0 0 votes

The key condition is:

$dist[w]>dist[v]+weight(v,w)$

This checks whether the path:

$source\rightarrow\cdots\rightarrow v\rightarrow w$

is shorter than the best currently known path to $w$.

If so, it performs:

$dist[w]=dist[v]+weight(v,w)$

This operation is called edge relaxation.

The new tentative distance is then inserted into a priority queue.

This is the central operation of Dijkstra's algorithm.

$\therefore$ Answer: D

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

Related questions

4 4 votes
1 1 answer
117
117 views
GO Classes asked Aug 24
117 views
GO Classes DPP | GATE CS, DA | Algorithms | Minimum Spanning Trees
Consider the statement:The minimum spanning tree of a connected weighted graph $G$ is unique if and only if all edge weights in $G$ are distinct.True False
2 2 votes
1 1 answer
144
144 views
GO Classes asked Aug 24
144 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide & Conquer
Consider three recursive algorithms.Algorithm $\mathbf{1}$Divides a problem of size $N$ into two subproblems of size $N/2$ and performs constant additional work.$T_1(N)=2...
2 2 votes
1 1 answer
111
111 views
GO Classes asked Aug 24
111 views
GO Classes DPP | GATE CS, DA | Algorithms | Selection Algorithms
Let, $L=\langle r_1,r_2,\ldots,r_n\rangle$ be an arbitrary list of integers, not necessarily distinct.Which of the following statements is incorrect?There exists an optim...
2 2 votes
1 1 answer
114
114 views
GO Classes asked Aug 24
114 views
GO Classes DPP | GATE CS, DA | Algorithms | Complexity Analysis
Consider the following recursive function $\texttt{Pot}$, which computes $x^n$, where $x$ is real and $n$ is an integer.Pot(x, n): if x == 0: return 0 if n == 0: return 1...