dijkstra Questions
9
Solved
I am trying to understand why Dijkstra's algorithm will not work with negative weights. Reading an example on Shortest Paths, I am trying to figure out the following scenario:
2
A-------B
\ /
3 ...
Dick asked 23/7, 2011 at 8:19
8
I'm working on Dijkstra's algorithm, and I really need to find all the possible shortest paths, not just one. I'm using an adjacency matrix and I applied Dijkstra's algorithm, and I can find the sh...
3
I need it for an implementation of Dijkstra's algorithm, and I do have my own implementation but documenting my code would be easier with java's own classes.
Semitrailer asked 27/4, 2012 at 7:29
6
Solved
I keep trying to google this, but the results I'm finding are just adding to my confusion. It seems that it can be possibly used for both? If so, which is it designed for by default and what needs ...
5
Solved
I'm trying to implement Dijkstra's algorithm in Java (self-study). I use the pseudo-code provided by Wikipedia (link). Now near the end of the algorithm, I should decrease-key v in Q;. I guess i sh...
2
Solved
Seeking an algorithm that will yield N short paths.
Does anyone have experience with an algorithm to find multiple short paths in a directed graph? My application is for language (finding synonym c...
Popularize asked 1/3, 2021 at 22:22
1
Solved
Dijkstra time complexity is O(V+ElogV) with binary heaps.
But, C++ pq(if used as binary heap), does not support decrease key. One solution suggested is to just insert the same vertex again in pq wi...
2
For my studies I have to write the following function which gets the shortest route between two countries. I already have already written a function isRoute which checks if there is a connection be...
4
Solved
I know there are two ways to represent my graph: one is using a matrix, and the other one is using a list.
If I use a matrix, I have to flip all the bits in the matrix. Doesn't that take O(V^2) ti...
Convivial asked 23/4, 2013 at 0:23
4
Solved
I wrote this implementation of Dijksta's Algorithm, which at each iteration of the loop while Q is not empty instead of finding the minimum element of the queue it takes the head of the queue.
Her...
Sheets asked 4/1, 2013 at 14:53
2
I'm studying about DFS and Dijkstra.
In my simple test cases, most of them shows that DFS is faster.
Passing every nodes costs the same in my test cases.
But most people prefer Dijkstra to DFS in p...
Hemorrhoidectomy asked 7/12, 2017 at 9:25
2
Solved
I use a matrix d to present a graph. d.(i).(j) means the distance between i and j; v denotes the number of nodes in the graph.
It is possible that there is negative cycle in this graph.
I would l...
Welloff asked 3/6, 2013 at 13:52
3
Solved
Typically, in Dijkstra's algorithm, for each encountered node, we check whether that node was processed before attempting to update the distances of its neighbors and adding them to the queue. This...
Newsy asked 17/3, 2020 at 18:58
5
I think that Dijkstra's algorithm is determined, so that if you choose the same starting vertex, you will get the same result (the same distances to every other vertex). But I don't think that it i...
Dystrophy asked 24/2, 2020 at 15:32
3
It's stated in a book that "Dijkstra's algorithm only works with Directed Acyclic Graphs".
It appears the algorithm works for graphs with cycles too as long as there are no negative cycles. Is th...
Pincer asked 13/4, 2017 at 14:23
9
I've read in one of my AI books that popular algorithms (A-Star, Dijkstra) for path-finding in simulation or games is also used to solve the well-known "15-puzzle".
Can anyone give me some pointer...
Xl asked 18/9, 2008 at 17:56
5
Solved
I know that could be asked before already but I cannot find it.
I need to modify below dijkstra algorithm which works good for finding
shortest path between 2 nodes but I need to find all possible ...
Ketene asked 14/4, 2013 at 18:55
3
Solved
Dijkstra's algorithm was taught to me was as follows
while pqueue is not empty:
distance, node = pqueue.delete_min()
if node has been visited:
continue
else:
mark node as visited
if node == ...
Lanni asked 13/2, 2012 at 4:29
1
Solved
I using this exact code for this. I modified it a little. So far I added a start and end node index to the calculateShortestDistances() method. Also the path ArrayList for collecting the path node ...
Northwestwards asked 4/8, 2019 at 15:11
2
Solved
I was working through http://youtu.be/gGQ-vAmdAOI?t=23m14s when at 23:14 I felt that branch & bound with an "extended list" was very similar to Dijkstra's algorithm. Later on in the lecture whe...
Ivanaivanah asked 23/12, 2014 at 16:31
2
Solved
Go, Dijkstra : print out the path, not just calculate the shortest distance.
http://play.golang.org/p/A2jnzKcbWD
I was able to find the shortest distance using Dijkstra algorithm, maybe not.
The ...
Antonioantonius asked 11/11, 2013 at 7:22
1
Solved
I'm trying to solve the bus routing problem in postgresql which requires visibility of previous and next rows. Here is my solution.
Step 1) Have one edges table which represents all the edges (the ...
Acord asked 27/9, 2018 at 13:6
5
Solved
I was asked this question in an interview, but I couldn't come up with any decent solution. So, I told them the naive approach of finding all the cycles then picking the cycle with the least length...
2
Solved
In Dijkstra's shortest path algorithm and others, to examine an edge to see if it offers a better path to a node is referred to as relaxing the edge. Why is it called relaxing?
Whitefaced asked 24/5, 2012 at 23:38
5
I need to modify Dijkstra's algorithm so that if there are several shortest paths I need to find the one with minimum number of edges on the path.
I've been stuck on how to use Dijkstra's method t...
Problem asked 18/11, 2013 at 7:1
© 2022 - 2024 — McMap. All rights reserved.