dijkstra Questions
14
Solved
Can somebody tell me why Dijkstra's algorithm for single source shortest path assumes that the edges must be non-negative.
I am talking about only edges not the negative weight cycles.
Playoff asked 31/10, 2012 at 13:41
3
Solved
I need to find the shortest route between 2 vertices of a graph. I have a matrix, which contains all the weights. How can I do it? Currently, I have the following code:
private int[] Dijkstra(int...
8
Solved
I am writing code of dijkstra algorithm, for the part where we are supposed to find the node with minimum distance from the currently being used node, I am using a array over there and traversing i...
1
Solved
I started using Dijkstra's algorithm in python using Networkx, but now I want to speed up my code using c++ and I chose Boost to work with graphs. My surprise was that I didn't see any speed up and...
Deadradeadweight asked 11/10, 2023 at 16:14
4
My goal is to find the shortest path (lowest cost) between given cities (vertices) connected with roads (edges).
Each road and each city has charge (cost) that has to be paid before entering that r...
Ytterbia asked 4/12, 2016 at 14:21
5
Solved
If I have a weighted undirected Graph with no negative weights, but can contain multiple edges between vertex and self-loops, Can I run Dijkstra algorithm without problem to find the minimum path b...
Gwenette asked 28/5, 2016 at 22:40
11
Solved
I have a undirected graph with about 100 nodes and about 200 edges. One node is labelled 'start', one is 'end', and there's about a dozen labelled 'mustpass'.
I need to find the shortest path thro...
Evelyn asked 21/10, 2008 at 16:1
18
What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?
Phrenology asked 3/1, 2013 at 17:45
4
Solved
I am trying to develop an algorithm to solve a problem that I am not able to classify, I expose the subject:
You have a map divided into sections that have a certain area and where a certain number...
Chongchoo asked 11/2, 2023 at 21:9
2
Is Dijkstra faster when using Fibonacci heap than with the Binary heap?
I did some experiments implementing Fibonacci heap on my own and using it in Dijkstra, I also checked the ready-to-use Fibona...
Casandra asked 6/7, 2022 at 18:41
5
I have read the following but please take a look at my code below.
Why Dijkstra's Algorithm uses heap (priority queue)?
I have two versions of dijkstra, one good version with PQueue, and one...
7
Solved
I am trying to find out if it is possible to use Dijkstra's algorithm to find the longest path in a directed acyclic path. I know that it is not possible to find the longest path with Dijkstra in a...
Citron asked 6/11, 2011 at 13:10
7
Solved
Both can be used to find the shortest path from single source. BFS runs in O(E+V), while Dijkstra's runs in O((V+E)*log(V)).
Also, I've seen Dijkstra used a lot like in routing protocols.
Thus, w...
Outpour asked 29/9, 2010 at 0:56
13
I am trying to implement Dijkstra's algorithm in python using arrays. This is my implementation.
def extract(Q, w):
m=0
minimum=w[0]
for i in range(len(w)):
if w[i]<minimum:
minimum=w[i]
m...
3
The time complexity for Dijkstra Algorithm using an array is O(V^2) and if priority queue is implemented, we can further improve the complexity to O(E log V). But what about its space complexity? I...
Alanealanine asked 14/6, 2018 at 11:24
8
Solved
As per my understanding, I have calculated time complexity of Dijkstra Algorithm as big-O notation using adjacency list given below. It didn't come out as it was supposed to and that led me to unde...
Wooster asked 24/10, 2014 at 12:24
5
Solved
I was reading about Graph algorithms and I came across these two algorithms:
Dijkstra's algorithm
Breadth-first search
What is the difference between Dijkstra's algorithm and BFS while looking fo...
Racquelracquet asked 22/8, 2014 at 14:46
8
Solved
After a lot of Googling, I've found that most sources say that the Dijkstra algorithm is "more efficient" than the Bellman-Ford algorithm. But under what circumstances is the Bellman-Ford algorithm...
Sauceda asked 20/10, 2013 at 20:13
4
Solved
On the Wikipedia page for Dijkstra's algorithm, they mark visited nodes so they wouldn't be added to the queue again. However, if a node is visited then there can be no distance to that node that i...
Macaroni asked 10/11, 2013 at 20:6
1
I have an issue I just can't get my head around...
I have a table called country_neighbour looking like this.
Country_name
Country_id
Neighbour_name
Neighbour_id
Italy
1
France
2
Italy
1
...
Rollicking asked 11/7, 2015 at 18:40
1
Solved
What is the time complexity of this particular implementation of Dijkstra's algorithm?
I know several answers to this question say O(E log V) when you use a min heap, and so does this article and t...
Aldosterone asked 21/12, 2021 at 5:36
12
Solved
I was looking at what the guys in the Mario AI Competition have been doing and some of them have built some pretty neat Mario bots utilizing the A* (A-Star) Pathing Algorithm.
(Video of Mario A*...
Bertilla asked 26/8, 2009 at 5:15
1
I have a large osmnx (networkx) graph and nx.all_pairs_dijkstra_path_length is taking a long time to calculate.
What possibilities are there to speed up the calculation?
Pluckless asked 20/10, 2021 at 16:12
4
Solved
So first let's define Dijkstra algorithm:
Dijkstra's algorithm finds single-source shortest paths in a directed graph with non-negative edge weights.
I want to know how can I save the shortest path...
Amortizement asked 11/3, 2015 at 22:29
2
Solved
How do I select the node that minimizes the maximum shortest distance to the other nodes in a graph?
I have an undirected, connected, positively-weighted graph G = <V,E>. I need to find one node v_min in V such that the maximum distance between v_min and the other nodes are minimized. I've l...
Winder asked 17/8, 2021 at 3:52
1 Next >
© 2022 - 2024 — McMap. All rights reserved.