Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged dijkstras-algorithm
0
votes
0
answers
31
Self Doubt
Dijkstra Algo terminates and produce wrong result when graph contain negative wt Cycle What about Belman Ford??and FloydWarshall???
Dijkstra Algo terminates and produce wrong result when graph contain negative wt CycleWhat about Belman Ford??and FloydWarshall???
Abhisek Tiwari 4
178
views
Abhisek Tiwari 4
asked
Nov 28, 2018
Algorithms
dijkstras-algorithm
graph-algorithm
+
–
0
votes
0
answers
32
#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
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 pa...
OneZero
355
views
OneZero
asked
Nov 28, 2018
Algorithms
dijkstras-algorithm
time-complexity
+
–
1
votes
0
answers
33
made easy
Piyush mishra
339
views
Piyush mishra
asked
Nov 26, 2018
Algorithms
dijkstras-algorithm
+
–
0
votes
1
answer
34
#doubt
difference between Bellmann ford and dijkstra's algorithm for -ve weight cycle graph
difference between Bellmann ford and dijkstra's algorithm for -ve weight cycle graph
amit166
360
views
amit166
asked
Nov 22, 2018
Algorithms
dijkstras-algorithm
+
–
0
votes
0
answers
35
ACE Test Series
ben10
593
views
ben10
asked
Nov 18, 2018
Algorithms
dijkstras-algorithm
+
–
0
votes
2
answers
36
METest_Algo
I think the past cost to G from A as computed by Dijkstra should be 2 instead of 8. Please help me verify it.
I think the past cost to G from A as computed by Dijkstra should be 2 instead of 8.Please help me verify it.
Ayush Upadhyaya
701
views
Ayush Upadhyaya
asked
Nov 18, 2018
Algorithms
algorithms
dijkstras-algorithm
made-easy-test-series
numerical-answers
+
–
0
votes
1
answer
37
self doubt about dijkistra algorithm negative cycle
Will dijkistra fail if a graph has negative weight cycle which is unreachable from source????
Will dijkistra fail if a graph has negative weight cycle which is unreachable from source????
adeemajain
261
views
adeemajain
asked
Nov 17, 2018
Algorithms
dijkstras-algorithm
+
–
0
votes
1
answer
38
Self doubt
What is the difference between Dijkstra and Bellman Ford algorithm? Will the shortest path given by both be same in following conditions : a) All positive edge weights b) Some negative edge weights without negative edge cycle c) With negative edge cycles
What is the difference between Dijkstra and Bellman Ford algorithm?Will the shortest path given by both be same in following conditions :a) All positive edge weightsb) So...
Vipin Rai
670
views
Vipin Rai
asked
Nov 11, 2018
Algorithms
dijkstras-algorithm
bellman-ford
greedy-algorithm
descriptive
+
–
0
votes
0
answers
39
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?)
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?)
srestha
516
views
srestha
asked
Oct 30, 2018
DS
dijkstras-algorithm
+
–
0
votes
0
answers
40
#testbook_testseries
Anil Ji
145
views
Anil Ji
asked
Sep 5, 2018
Algorithms
dijkstras-algorithm
+
–
0
votes
0
answers
41
Greedy Techniques
hello everyone, I think that that the worst case time complexity of the dijkstra's algorithm is O(Elog(V)) and for the situation when a complete graph is considered, this will change to O(V^2(log(V))). ..( i am following the heap , extract min, and decrease ... +V(logV)), which for the complete graph changed to O(n^2 + V(logV)). Please let me know if my reasoning is wrong.
hello everyone, I think that that the worst case time complexity of the dijkstra's algorithm is O(Elog(V)) and for the situation when a complete graph is considered, this...
hrcule
201
views
hrcule
asked
Sep 4, 2018
Algorithms
dijkstras-algorithm
+
–
0
votes
0
answers
42
Made easy test series
What is meant by wrong path in Dijikstra's algo. Can anyone please explain
What is meant by wrong path in Dijikstra's algo. Can anyone please explain
Ashok
246
views
Ashok
asked
Sep 2, 2018
Algorithms
dijkstras-algorithm
+
–
1
votes
2
answers
43
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
679
views
Rishav Kumar Singh
asked
Jul 29, 2018
Algorithms
greedy-algorithm
dijkstras-algorithm
+
–
2
votes
1
answer
44
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
Algorithms
dijkstras-algorithm
shortest-path
space-complexity
algorithms
graph-algorithm
greedy-algorithm
+
–
0
votes
1
answer
45
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
Which of the following statements related to graphs are True?Consider a graph with Positive distinct edges1.If we add a Positive Integer to all edges, then there are chan...
Balaji Jegan
682
views
Balaji Jegan
asked
Jun 9, 2018
Graph Theory
algorithms
graph-theory
dijkstras-algorithm
+
–
1
votes
1
answer
46
Dijkstra Time Complexity using Binary Heap
Question Source - https://gateoverflow.in/1374/gate2005-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: 1. O(|V|2) 2. O(| ... as I > said the correct answer is O((|E|+|V|)log|V|). So, where am I going > wrong?
Question Source - https://gateoverflow.in/1374/gate2005-38Let G(V,E)be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm ...
iarnav
2.5k
views
iarnav
asked
May 22, 2018
Algorithms
algorithms
binary-heap
dijkstras-algorithm
time-complexity
+
–
2
votes
1
answer
47
# Self doubt
To get in shape, you have decided to start running to work. You want a route that goes entirely uphill and then entirely downhill so that you can work up a sweat going uphill and then get a nice breeze at the end of your run as you ... Assuming that every road segment is either uphill or downhill, give an efficient algorithm to find out shortest route that meets above specification??
To get in shape, you have decided to start running to work. You want a route that goes entirely uphill and then entirely downhill so that you can work up a sweat going up...
G Shaheena
656
views
G Shaheena
asked
Apr 25, 2018
Algorithms
algorithms
shortest-path
dijkstras-algorithm
+
–
1
votes
1
answer
48
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
Algorithms
dijkstras-algorithm
shortest-path
+
–
1
votes
0
answers
49
Dijkstra's
Pawan Kumar 2
374
views
Pawan Kumar 2
asked
Jan 25, 2018
Algorithms
dijkstras-algorithm
+
–
1
votes
3
answers
50
Dijkstra Algorithm
I think answer should be Option(B). Path:<s,y><y,x><x,t> = 7-3-2=2
I think answer should be Option(B).Path:<s,y><y,x><x,t = 7-3-2=2
ankit_thawal
1.5k
views
ankit_thawal
asked
Jan 25, 2018
Algorithms
dijkstras-algorithm
shortest-path
algorithms
made-easy-test-series
+
–
2
votes
1
answer
51
Question
AnilGoudar
455
views
AnilGoudar
asked
Jan 10, 2018
Algorithms
algorithms
dijkstras-algorithm
test-series
+
–
1
votes
2
answers
52
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.1k
views
pranab ray
asked
Jan 3, 2018
Algorithms
algorithms
dijkstras-algorithm
graph-algorithm
+
–
1
votes
1
answer
53
Dijkstra's Algorithm
Let G(V,E) an undirected graph with positive edge weights . Dijkstras single source algorithm can be implemented using the sorted linked list data structure and adjacency list . What is the time complexity? a) O(E|V|) b)O(|V|^3) c)O(|V|log|v|) d)O((|E|+|V|)log|V|)
Let G(V,E) an undirected graph with positive edge weights . Dijkstras single source algorithm can be implemented using the sorted linked list data structure and adjacency...
Abhinavg
1.8k
views
Abhinavg
asked
Nov 29, 2017
Algorithms
dijkstras-algorithm
time-complexity
+
–
–1
votes
1
answer
54
Dijkstra algorithm
Parshu gate
1.4k
views
Parshu gate
asked
Nov 28, 2017
Computer Networks
dijkstras-algorithm
shortest-path
computer-networks
+
–
3
votes
0
answers
55
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 ?
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...
Hitoshi
1.6k
views
Hitoshi
asked
Oct 15, 2017
Algorithms
algorithms
dijkstras-algorithm
graph-theory
+
–
7
votes
0
answers
56
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.
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...
junaid ahmad
1.9k
views
junaid ahmad
asked
Oct 12, 2017
Algorithms
dijkstras-algorithm
shortest-path
+
–
1
votes
1
answer
57
ace test
What is cost of shortest path from S to T ? is any difference between when greedy method is used
What is cost of shortest path from S to T ?is any difference between when greedy method is used
ADITYA CHAURASIYA 5
1.5k
views
ADITYA CHAURASIYA 5
asked
Sep 28, 2017
Algorithms
dijkstras-algorithm
ace-test-series
+
–
0
votes
0
answers
58
Dikshtra
How to solve this?
How to solve this?
saumya mishra
140
views
saumya mishra
asked
Sep 25, 2017
Algorithms
dijkstras-algorithm
+
–
1
votes
3
answers
59
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.
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 inc...
Warlock lord
1.4k
views
Warlock lord
asked
Sep 14, 2017
Algorithms
dijkstras-algorithm
algorithms
shortest-path
+
–
0
votes
0
answers
60
Algorithm
Beyonder
292
views
Beyonder
asked
Aug 18, 2017
Algorithms
algorithms
dijkstras-algorithm
breadth-first-search
+
–
Page:
« prev
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register