Recent questions tagged dijkstras-algorithm / GATE Overflow for GATE CSE

0 votes

0 answers

1

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

363 views

sonalrawat asked Aug 21, 2023

2 votes

1 answer

2

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

697 views

GO Classes asked Mar 26, 2023

0 votes

0 answers

3

Dijkstra Algorithm

Elaf

316 views

Elaf asked Jan 22, 2023

0 votes

0 answers

4

Topic - Dijkstra Algorithm Question 5a

gate20232

480 views

gate20232 asked Jan 18, 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

1 answer

6

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

656 views

palashbehra5 asked Jan 11, 2022

0 votes

1 answer

7

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

4 votes

1 answer

8

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

9

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

2 votes

1 answer

10

Made Easy Test Series:Algorithm-Dijkstra
Which of the following procedure results same output as Dijkstra’s Algo. on unweighted graph on $'n'$ verices? $A)$ BFS $B)$ DFS $C)$Kruskal $D)$ Prims As far I know Dijkstra and Prims both have $T.C.=O(E+VlogV)$ But ans given BFS. How this ans possible??

Which of the following procedure results same output as Dijkstra’s Algo. on unweighted graph on $'n'$ verices?$A)$ BFS $B)$ DFS $C)$Kruskal $D)$ PrimsAs far I know ...

srestha

839 views

srestha asked May 18, 2019

0 votes

2 answers

11

Made Easy Workbook
Suppose that you are running Dijkstra’s algorithm on the edge-weighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of each vertex after vertex E has been deleted from the priority queue and relaxed. Vertex Distance Parent A 0 Null B 2 A C 13 F D 23 A E 11 F F 7 B G 36 F H 19 E What could be the possible value of expression x+y?

Suppose that you are running Dijkstra’s algorithm on the edge-weighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of ...

noob_coder

2.2k views

noob_coder asked Mar 10, 2019

0 votes

2 answers

12

made easy
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?

can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?

screddy1313

708 views

screddy1313 asked Jan 26, 2019

0 votes

1 answer

13

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

0 votes

0 answers

14

Dijkstra's Algorithm on negative weight cycle
Somebody please clarify me, will dijkstra’s algorithm terminate if there is a negative cycle present? (as far as I know, it doesn't give correct result as it keep updating the value, so in that logic it sould fall into infinite loop and wont terminate. Is this correct?)

Somebody please clarify me, will dijkstra’s algorithm terminate if there is a negative cycle present? (as far as I know, it doesn't give correct result as it keep updat...

anisha007

1.7k views

anisha007 asked Jan 24, 2019

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

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