Search results for dijkstras-algorithm / GATE Overflow for GATE CSE

37 votes

3 answers

1

GATE CSE 2004 | Question: 44
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$

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

Kathleen

15.5k views

Kathleen asked Sep 18, 2014

0 votes

0 answers

2

Consider the following strategy to convert an undirected graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, update the weight to w+k+1. Consider the following claim: To solve the shortest path problem in the original graph, we can run Dijkstra's algorithm on the modified graph and subtract the added weights to get the original distances. Which of the following is not correct. The claim is not true in general. The claim is not true in general for graphs with cycles. The claim is true for connected acyclic graphs. The claim is true for all graphs.

sonalrawat

365 views

sonalrawat asked Aug 21, 2023

2 votes

1 answer

3

GO Classes 2023 | IIITH Mock Test 1 | Question: 10
$\text{G}$ is a directed graph with negative weight edges but NO negative weight cycles. Which of the following hold for Dijkstra's algorithm on $\text{G}:$ Dijkstra's algo will always give the correct output since there is no ... if we add large positive weight to every edge then it will work. Dijkstra's algo may not terminate in this case.

$\text{G}$ is a directed graph with negative weight edges but NO negative weight cycles. Which of the following hold for Dijkstra’s algorithm on $\text{G}:$Dijkstra’s...

GO Classes

702 views

GO Classes asked Mar 26, 2023

0 votes

0 answers

4

Dijkstra Algorithm

Elaf

316 views

Elaf asked Jan 22, 2023

1 votes

1 answer

5

Dijkstra's algorithm | Negative Weight Cycle
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUE FALSE

If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE

Souvik33

697 views

Souvik33 asked Dec 19, 2022

0 votes

0 answers

6

Topic - Dijkstra Algorithm Question 5a

gate20232

481 views

gate20232 asked Jan 18, 2023

25 votes

7 answers

7

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.6k views

Kathleen asked Oct 9, 2014

0 votes

1 answer

8

Nptel Assignment Question
Consider the following strategy to convert a graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, ... all graphs. The claim is true for connected acyclic graphs. The claim is not true in general for connected graphs with cycles

Consider the following strategy to convert a graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge wei...

rsansiya111

1.2k views

rsansiya111 asked Dec 8, 2021

0 votes

1 answer

9

Single Source Shortest Path | Made Easy Full Syllabus Test
The answer they have given is 2, but i think it should be 1, can someone verify?

The answer they have given is 2, but i think it should be 1, can someone verify?

palashbehra5

657 views

palashbehra5 asked Jan 11, 2022

1 votes

1 answer

10

Negative edge weights in Dijkstra
All text books and online resources say Dijkstra's algorithm need all non negative edge weights However I feel a bit different, especially after coming across problem asking to build shortest path tree from node aa in following graph: My shortest path ... -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?

All text books and online resources say Dijkstra's algorithm need all non negative edge weightsHowever I feel a bit different, especially after coming across problem aski...

GateAspirant999

3.5k views

GateAspirant999 asked Feb 1, 2018

1 votes

2 answers

11

Doubt
What is Dijkstra's algorithm running time using sorted array?

What is Dijkstra's algorithm running time using sorted array?

Shreya Roy

482 views

Shreya Roy asked Dec 20, 2016

4 votes

1 answer

12

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 45
What is time complexity of Dijkstra's algorithm if we use sorted linked list instead of min-heap or priority queue. Assume graph $G(V,E)$ is represented by an adjacency list and $|V| = v$ and $|E| = e.$ $\Theta((v + e)\log v)$ $\Theta(v^2 + e \log v)$ $\Theta(v . e)$ $\Theta(v^2)$

What is time complexity of Dijkstra's algorithm if we use sorted linked list instead of min-heap or priority queue. Assume graph $G(V,E)$ is represented by an adjacency l...

gatecse

459 views

gatecse asked Feb 1, 2021

0 votes

4 answers

13

UGC NET CSE | January 2017 | Part 3 | Question: 35
Dijkstra’s algorithm is based on Divide and conquer paradigm Dynamic programming Greedy approach Backtracking paradigm

Dijkstra’s algorithm is based onDivide and conquer paradigmDynamic programmingGreedy approachBacktracking paradigm

go_editor

2.2k views

go_editor asked Mar 24, 2020

1 votes

2 answers

14

Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
Suppose that you implement Dijkstra's algorithm using a priority queue algorithm that requires O(V ) time to initialize, worst-case f(V, E) time for each EXTRACT-MIN operation and worst-case g(V, E) time for each DECREASE- ... (worst-case) time does it take to run Dijkstra's algorithm on an input graph G = (V, E)?.

Suppose that you implement Dijkstra’s algorithm using a priority queue algorithm that requires O(V ) time to initialize, worst-case f(V, E) time for each EXTRACT-MIN op...

Rishav Kumar Singh

706 views

Rishav Kumar Singh asked Jul 29, 2018

4 votes

1 answer

15

GATE Overflow | Mock GATE | Test 1 | Question: 47
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs ... , S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct

Which of the following statements is/are correct with respect to Djikstra Algorithm?(P) It always works perfectly for graphs with negative weight edges.(Q) It does not wo...

Ruturaj Mohanty

1.6k views

Ruturaj Mohanty asked Dec 27, 2018

1 votes

2 answers

16

Dijkstra’s algorithms
Consider a weighted, directed acyclic graph G = (V,E,w) in which edges that leave the source vertex s may have negative weights and all other edge weights are nonnegative. Does Dijkstra’s algorithm correctly compute the shortest-path weight δ(s,t) from s to every vertex t in this graph? Justify your answer

Consider a weighted, directed acyclic graph G = (V,E,w) in which edges that leave the source vertex s may have negative weights and all other edge weights are nonnegative...

pranab ray

1.2k views

pranab ray asked Jan 3, 2018

2 votes

3 answers

17

selfmade
Suppose we have a graph with a negative weight cycle reaching from the source. And if we try to compute shortest path using Dijkstra's algorithm which of the following is likely to happen? A) May not find shortest path but report the presence of negative cycle B) Algorithm never terminates may go to an infinite loop C) Algorithm terminates D) None

Suppose we have a graph with a negative weight cycle reaching from the source. And if we try to compute shortest path using Dijkstra's algorithm which of the following is...

Jithin Jayan

715 views

Jithin Jayan asked Nov 3, 2016

2 votes

1 answer

18

Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????

I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity)But how ????

Hardik Maheshwari

3.0k views

Hardik Maheshwari asked Jul 5, 2018

2 votes

1 answer

19

Question

AnilGoudar

468 views

AnilGoudar asked Jan 10, 2018

0 votes

1 answer

20

ME Test Series Question
Consider the following statements given below: S1 : If a graph contain a negative weight cycle then Dijkstra’s algorithm may or may not terminate. S2 : Bellman Ford algorithm for every weighted graph which contain two vertices u and v always produces a shortest path. Which of the above statements are incorrect? Only S1 Only S2 Both S1 and S2 None of these

Consider the following statements given below:S1 : If a graph contain a negative weight cycle then Dijkstra’s algorithm may or may not terminate.S2 : Bellman Ford algor...

Shankar Kakde

3.0k views

Shankar Kakde asked Jan 25, 2019

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