The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged dijkstrasalgorithm
0
votes
1
answer
1
Made Easy Workbook
Suppose that you are running Dijkstra’s algorithm on the edgeweighted 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?
asked
Mar 10, 2019
in
Algorithms
by
noob_coder
Junior
(
785
points)

333
views
algorithms
graphalgorithms
dijkstrasalgorithm
0
votes
2
answers
2
made easy
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
asked
Jan 26, 2019
in
Algorithms
by
screddy1313
(
481
points)

82
views
graphalgorithms
dijkstrasalgorithm
programminginc
0
votes
0
answers
3
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?)
asked
Jan 25, 2019
in
Algorithms
by
anisha007
(
209
points)

159
views
dijkstrasalgorithm
0
votes
0
answers
4
#SELF DOUBT
Prove dijkstra’s algorithm using Heap is O((n+E)logn) where n is no.of vertices and E is number of edges? Book : Fundamentals of Computer Algorithms By sahni page : 263
asked
Nov 28, 2018
in
Algorithms
by
OneZero
Active
(
2.1k
points)

35
views
dijkstrasalgorithm
timecomplexity
0
votes
0
answers
5
Data Structure Decrease Key Extract Min
Why Decrease Key operation we do only on edges and Extract Min operation do only on vertices? (I mean why Decrease key cannot operate on both edges and vertices?)
asked
Oct 30, 2018
in
DS
by
srestha
Veteran
(
119k
points)

116
views
dijkstrasalgorithm
+1
vote
1
answer
6
Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo
asked
Jul 30, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.7k
points)

138
views
greedyalgorithm
dijkstrasalgorithm
+1
vote
1
answer
7
Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithmspacetimecomplexity) But how ????
asked
Jul 5, 2018
in
Algorithms
by
Hardik Maheshwari
(
101
points)

634
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
0
votes
1
answer
8
True/False
Which of the following statements related to graphs are True? Consider a graph with Positive distinct edges 1.If we add a Positive Integer to all edges, then there are chances to get more than one shortest paths between 2 vertices 2.If we add a Positive Integer ... 4.If we add a Negative Integer to all edges, then there are chances to get more than one longest paths between 2 vertices
asked
Jun 9, 2018
in
Graph Theory
by
Balaji Jegan
Active
(
5k
points)

98
views
algorithms
graphtheory
dijkstrasalgorithm
0
votes
1
answer
9
Made easy workbook
asked
Jun 2, 2018
in
Algorithms
by
anjali.it25
(
19
points)

120
views
dijkstrasalgorithm
+1
vote
1
answer
10
Dijkstra Time Complexity using Binary Heap
Question Source  https://gateoverflow.in/1374/gate200538 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: 1. O(V2) 2. O( ... as I > said the correct answer is O((E+V)logV). So, where am I going > wrong?
asked
May 22, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

322
views
algorithms
binaryheap
dijkstrasalgorithm
timecomplexity
heap
+1
vote
0
answers
11
Dijkstra's
asked
Jan 26, 2018
in
Algorithms
by
Pawan Kumar 2
Active
(
4.2k
points)

69
views
dijkstrasalgorithm
+1
vote
0
answers
12
Question
asked
Jan 10, 2018
in
Algorithms
by
AnilGoudar
Active
(
4.4k
points)

43
views
algorithms
dijkstrasalgorithm
+1
vote
1
answer
13
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 shortestpath weight δ(s,t) from s to every vertex t in this graph? Justify your answer
asked
Jan 3, 2018
in
Algorithms
by
pranab ray
Junior
(
785
points)

128
views
algorithms
dijkstrasalgorithm
graphalgorithms
+3
votes
2
answers
14
Dijkstra Algorithm
asked
Dec 5, 2017
in
Algorithms
by
Parshu gate
Active
(
3.1k
points)

498
views
dijkstrasalgorithm
shortestpath
algorithms
–1
vote
1
answer
15
Dijkstra algorithm
asked
Nov 29, 2017
in
Computer Networks
by
Parshu gate
Active
(
3.1k
points)

320
views
dijkstrasalgorithm
shortestpath
computernetworks
+3
votes
0
answers
16
Self Doubt ( Decrease key operation )
While going through dijkstra's algorithm, there is a term "decrease key". I am not getting the meaning when it says "we do decrease key operation". What exactly we do and what is the meaning of decrease key ?
asked
Oct 15, 2017
in
Algorithms
by
Hitoshi
(
53
points)

593
views
algorithms
dijkstrasalgorithm
graphtheory
+7
votes
0
answers
17
Dijkstra's
I know that Dijkstra's Doesn't work for Negative weight cycle because it form a loop, Does it also true that it may or may not work for negative weight edge(without cycle) ? If it is not working for a negative weight edge(without cycle) give some example to prove it.
asked
Oct 12, 2017
in
Algorithms
by
junaid ahmad
Loyal
(
8.6k
points)

691
views
dijkstrasalgorithm
shortestpath
0
votes
3
answers
18
dijkstra
If we run Dijkstra’s algorithm to find single source shortest path for the above edge weighted directed graph with ‘8’ as source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized.
asked
Sep 14, 2017
in
Algorithms
by
Warlock lord
Active
(
3.3k
points)

259
views
dijkstrasalgorithm
algorithms
shortestpath
0
votes
0
answers
19
Algorithm
asked
Aug 18, 2017
in
Algorithms
by
Beyonder
(
499
points)

62
views
algorithms
dijkstrasalgorithm
bfs
+1
vote
2
answers
20
confused somebody please tell this Dijkstra
asked
Apr 10, 2017
in
Computer Networks
by
LavTheRawkstar
Active
(
3.8k
points)

117
views
computernetworks
dijkstrasalgorithm
+1
vote
1
answer
21
#Totally Confused# please tell Using Dijkstra Algorithm solve shortest path algorithm from A to D.
asked
Apr 6, 2017
in
Computer Networks
by
LavTheRawkstar
Active
(
3.8k
points)

237
views
algorithms
shortestpath
dijkstrasalgorithm
computernetworks
+1
vote
1
answer
22
MadeEasy Subject Test: Algorithms  Graph Algorithms
Which of the following statements is true? Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights. Complete graph with 4 vertices, each edges ... ). None of these how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right?
asked
Jan 20, 2017
in
Algorithms
by
Pankaj Joshi
Active
(
2.7k
points)

716
views
madeeasytestseries
algorithms
graphalgorithms
dijkstrasalgorithm
0
votes
0
answers
23
Doubt
What is Dijkstra's algorithm running time using sorted array?
asked
Dec 20, 2016
in
Algorithms
by
Shreya Roy
Active
(
4.5k
points)

75
views
dijkstrasalgorithm
+2
votes
1
answer
24
Analysis of Dijikstra Algorithm
What will be the change is Time Complexity OF Dijikstra Algorithm If Following Data Structures are used ? Priority Queue : Binary Heap & Graph : Matrix Priority Queue : Binomial Heap & Graph : Adjacancy List Priority Queue : Fibonacci Heap & ... : AVL Tree & Graph : Adjacancy List How to find the change in timecomplexity if one is used over the other
asked
Dec 14, 2016
in
Algorithms
by
PEKKA
Active
(
1.9k
points)

435
views
algorithms
dijkstrasalgorithm
+1
vote
1
answer
25
MadeEasy Test Series: Algorithms  Graph Algorithms
asked
Dec 14, 2016
in
Algorithms
by
rahul sharma 5
Boss
(
25.6k
points)

158
views
madeeasytestseries
algorithms
graphalgorithms
shortestpath
dijkstrasalgorithm
+1
vote
0
answers
26
[Algrithms] Dijkstra Time complexity
From Wikipedia : the algorithm requires time in the worst case; for connected graphs this time bound can be simplified to 1. Can somebody explain how are we combing (V+E) into E in case of connected graph and why it can't be combined in case of disconnected graph? 2. What will be dijakstra behaviour for disconnected graph?
asked
Dec 11, 2016
in
Algorithms
by
rahul sharma 5
Boss
(
25.6k
points)

237
views
dijkstrasalgorithm
+4
votes
1
answer
27
dijkstra
Which of the following statements is/are True? I.Consider a weighted directed graph G and let ‘P’ be a shortest path from u to v for u,v∈V. If we double the weight of every edge in the graph for each ‘e’ belongs to E, then P will still be a shortest path from u to v. II.The time complexity to detect negative weight cycles in an arbitrary directed graph is O(V+E).
asked
Nov 28, 2016
in
Algorithms
by
Shubham Pandey 2
Loyal
(
6.9k
points)

429
views
dijkstrasalgorithm
0
votes
0
answers
28
dijkstra
Consider a Graph G which contains a negative weight edges but not negative cycles then which of the following statements is TRUE when we run Dijkstra's algorithm? It may not terminate It terminates but may produce incorrect results. Explanation: It always ... + e priority queue operations, but may produce incorrect results It never terminates due to cycles in graph None of these
asked
Nov 28, 2016
in
Algorithms
by
Shubham Pandey 2
Loyal
(
6.9k
points)

541
views
dijkstrasalgorithm
+5
votes
1
answer
29
Dijkstra's algorithm
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?
asked
Nov 5, 2016
in
Algorithms
by
vaishali jhalani
Active
(
4.8k
points)

933
views
algorithms
dijkstrasalgorithm
graphalgorithms
shortestpath
+1
vote
1
answer
30
Dijkstra's Agorithm
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?
asked
Nov 4, 2016
in
Algorithms
by
vaishali jhalani
Active
(
4.8k
points)

347
views
algorithms
dijkstrasalgorithm
graphalgorithms
shortestpath
Page:
1
2
next »
Quick search syntax
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
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged dijkstrasalgorithm
Recent Blog Comments
100 percent
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....
absolutely right
50,737
questions
57,287
answers
198,197
comments
104,874
users