Dijkstraandrsquo;s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer?

EduRev

All Courses

Explore Courses UPSC Exam UPSC Test Series Free Notes EduRev Infinity

Open App

GATE Exam > GATE Questions > Dijkstra’s single source shortest path ...

Join the Discussion on the App

Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;

a)
only vertex a
b)
only vertices a, e, f, g, h
c)
only vertices a, b, c, d
d)
all the vertices

Correct answer is option 'D'. Can you explain this answer?

FREE This question is part of

Computer Science And IT (CS/IT) Mock Test For Gate

Attempt Test

Attempt this Test

Verified Answer

Dijkstra’s single source shortest path algorithm when run from v...

Dijkstra's single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.

Let us see...

Let us run the 1st pass b 1 b is minimum, so shortest distance to b is 1

After 1st pass, distances are c 3. e -2. e is minimum, so shortest distance toe is -2 After 2nd pass, distances are c 3, f 0. f is minimum, so shortest distance t of is 0 After 3rd pass, distances are c 3, g 3. Both are same, let us take g. so shortest distance to g is 3. After 4th pass, distances are c 3, h 5 c is minimum, so shortest distance to c is 3 After 5th pass, distances are h -2 h is minimum, so shortest distance to h is -2.

View all questions of this test

View all answers Start learning for free

< Previous Question Next Question >

Explore Courses for GATE exam

Similar GATE Doubts

Let G = (V, E ) be a directed, weighted graph with weight function w : E → R. For some function f : V → R, for each edge (u , v ) ∈ E, define w ′(u , v ) as w (u , v ) + f (v ).Which one of the options completes the following sentence so that it is TRUE?“The shortest paths in G under w are shortest paths under w′ too, ________”.

View answer

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 when a strictly shorter path to v is discovered.

View answer

If we run Dijkstra algorithm on vertex S to the following graph, then which of the following is shortest path distance from S to t

View answer

Consider the following statements about Dijkstra’s algorithm.1. Dijkstra’s algorithm produces an incorrect result only if the graph contains a negative weight cycle.2. If a graph contains a negative weight cycle, then Dijkstras algorithm may not terminate.Which of the above statements is true?

View answer

What is the time complexity of Bellman-Ford single-source shortest path algorithm on acomplete graph of n vertices?

View answer

Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer?

Share with a Friend

Answer this doubt

Question Description
Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer?.

Solutions for Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE. Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.

Here you can find the meaning of Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer?, a detailed solution for Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer? has been provided alongside types of Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to;a)only vertex ab)only vertices a, e, f, g, hc)only vertices a, b, c, dd)all the verticesCorrect answer is option 'D'. Can you explain this answer? tests, examples and also practice GATE tests.

Explore Courses for GATE exam