# Recent questions tagged dijkstras-algorithm

1
Dijkstra’s algorithm is based on Divide and conquer paradigm Dynamic programming Greedy approach Backtracking paradigm
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?
3
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
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?)
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
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
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?)
1 vote
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)?.
1 vote
9
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????
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
11
1 vote
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?
1 vote
13
1 vote
14
1 vote
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
16
–1 vote
17
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 ?
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.
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.
21
1 vote
22
1 vote
23
Using DIjkstra algorithm solve shortest path algorithm from A to D
1 vote
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?
1 vote
25
What is Dijkstra's algorithm running time using sorted array?
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
1 vote