search
Log In

Recent questions tagged dijkstras-algorithm

0 votes
2 answers
1
Dijkstra’s algorithm is based on Divide and conquer paradigm Dynamic programming Greedy approach Backtracking paradigm
asked Mar 24 in Algorithms jothee 96 views
0 votes
1 answer
2
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?
asked Mar 10, 2019 in Algorithms noob_coder 627 views
0 votes
2 answers
3
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
asked Jan 26, 2019 in Algorithms screddy1313 145 views
0 votes
0 answers
4
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 anisha007 369 views
3 votes
1 answer
5
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 with negative weight edges. (S) It ... Only P, Q, S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 282 views
0 votes
0 answers
6
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 OneZero 63 views
0 votes
0 answers
7
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 srestha 165 views
1 vote
2 answers
8
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-KEY operation. How much (worst-case) time does it take to run Dijkstra’s algorithm on an input graph G = (V, E)?.
asked Jul 30, 2018 in Algorithms Rishav Kumar Singh 255 views
0 votes
1 answer
10
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 to ... vertices 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 Balaji Jegan 142 views
0 votes
1 answer
11
1 vote
1 answer
12
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(|E|+|V|log|V|) 3. O(|V|log|V|) ... |V| = |E|, but as I > said the correct answer is O((|E|+|V|)log|V|). So, where am I going > wrong?
asked May 22, 2018 in Algorithms iarnav 583 views
1 vote
0 answers
13
asked Jan 26, 2018 in Algorithms Pawan Kumar 2 98 views
1 vote
1 answer
14
asked Jan 10, 2018 in Algorithms AnilGoudar 120 views
1 vote
2 answers
15
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
asked Jan 3, 2018 in Algorithms pranab ray 240 views
3 votes
2 answers
16
3 votes
0 answers
18
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 Hitoshi 911 views
7 votes
0 answers
19
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 junaid ahmad 982 views
0 votes
3 answers
20
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 Warlock lord 368 views
0 votes
0 answers
21
1 vote
1 answer
24
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 having same weights can have maximum ... no negative cycles). 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 Pankaj Joshi 1.2k views
1 vote
1 answer
25
What is Dijkstra's algorithm running time using sorted array?
asked Dec 20, 2016 in Algorithms Shreya Roy 102 views
3 votes
1 answer
26
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 & Graph : Adjacancy List Priority ... Priority Queue : 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 PEKKA 582 views
1 vote
0 answers
28
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 rahul sharma 5 329 views
4 votes
1 answer
29
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 Shubham Pandey 2 474 views
0 votes
0 answers
30
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 terminates ... + |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 Shubham Pandey 2 1.1k views
...