GATE CSE 2004 | Question: 44

Kathleen asked Sep 18, 2014 • edited Jan 3 by Hira Thakur

15,762 views

37 votes

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source.

In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

$P,Q,R,S,T,U$
$P,Q,R,U,S,T$
$P,Q,R,U,T,S$
$P,Q,T,R,U,S$

Algorithms
gatecse-2004
algorithms
graph-algorithms
normal
dijkstras-algorithm

+ –

Kathleen asked Sep 18, 2014 • edited Jan 3 by Hira Thakur

Kathleen

15.8k views

See all

1 1 comment

ritiksri8

commented Mar 16

0 votes

Please log in or register to add a comment.

Please log in or register to answer this question.

3 Answers

Best answer

33 votes

Answer is (B). In Dijkstra's algorithm at each point we choose the vertex with the shortest distance from the set of vertices in the shortest path found so far and add the edge connecting it to the shortest path.

gate_asp answered Mar 29, 2015 • edited Aug 24, 2022 by Arjun

gate_asp

See all

6 6 Comments

Show 3 previous comments

Subbu.

commented Aug 17, 2022

Choosing smallest edge in Dijkstra, ??

0 votes

Arjun

commented Aug 24, 2022

Fine now?

0 votes

Abhrajyoti00

commented Dec 8, 2022

The path visualized :-

1 votes

Please log in or register to add a comment.

10 votes

Answer will be "B"

Prateek kumar answered Nov 23, 2017

Prateek kumar

See all

0 Please log in or register to add a comment.

0 votes

Option B :

Biswanath answered Aug 22, 2023

Biswanath

See all

0 Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community

Answer:

← Previous Next →

← Previous in category Next in category →

Related questions

55 votes

11 answers

Kathleen asked Sep 18, 2014

11,952 views

GATE CSE 2004 | Question: 81
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$

Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected gr...

Kathleen

12.0k views

Kathleen asked Sep 18, 2014

Algorithms
gatecse-2004
algorithms
graph-algorithms
normal
graph-connectivity

+ –

25 votes

7 answers

Kathleen asked Oct 9, 2014

7,679 views

GATE CSE 1996 | Question: 17
Let $G$ be the directed, weighted graph shown in below figure We are interested in the shortest paths from $A$. Output the sequence of vertices identified by the Dijkstra's algorithm for single source shortest path when the algorithm is started at node $A$ Write down ... vertices in the shortest path from $A$ to $E$ What is the cost of the shortest path from $A$ to $E$?

Let $G$ be the directed, weighted graph shown in below figureWe are interested in the shortest paths from $A$.Output the sequence of vertices identified by the Dijkstra�...

Kathleen

7.7k views

Kathleen asked Oct 9, 2014

Algorithms
gate1996
algorithms
graph-algorithms
normal
dijkstras-algorithm
descriptive

+ –

66 votes

9 answers

gatecse asked Sep 26, 2014

27,027 views

GATE CSE 2012 | Question: 40
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only ... a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest...

gatecse

27.0k views

gatecse asked Sep 26, 2014

Algorithms
gatecse-2012
algorithms
graph-algorithms
normal
dijkstras-algorithm

+ –

54 votes

1 answer

Kathleen asked Sep 22, 2014

16,409 views

GATE CSE 2005 | Question: 38
Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: $O\left(|V|^2\right)$ $O\left(|E|+|V|\log |V|\right)$ $O\left(|V|\log|V|\right)$ $O\left(\left(|E|+|V|\right)\log|V|\right)$

Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure...

Kathleen

16.4k views

Kathleen asked Sep 22, 2014

Algorithms
gatecse-2005
algorithms
graph-algorithms
normal
dijkstras-algorithm

+ –

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

1 1 comment reply

Please log in or register to add a comment.

Please log in or register to answer this question.

3 Answers

6 6 Comments reply

Please log in or register to add a comment.

0 reply

Please log in or register to add a comment.

0 reply

Please log in or register to add a comment.

Related questions

1 1 comment

6 6 Comments

0

0