Questions tagged [dijkstras-algorithm]
The dijkstras-algorithm tag has no usage guidance.
11
questions with no upvoted or accepted answers
2
votes
0answers
36 views
Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph
As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
2
votes
0answers
104 views
For which class of graphs can a minimum spanning tree always be associated to a shortest path tree?
Given a connected graph $G=(X,E)$ with positive edge weights. We assume that $G$ contains a unique min weight spanning tree $T_{\min}$ (this is true for example when for all the cuts, the edge with ...
1
vote
0answers
49 views
Is dijkstra's algorithm fastest possible algorithm for undirected graph with no additional data?
there are many similar questions, but I haven't found direct answer to this question. Consider I have undirected, weighted graph with positive weights, no additional data - hence no heuristic (so it ...
1
vote
0answers
10 views
Node ordering at contraction hierarchy of biDirectional Dijkstra
I try to understand the node ordering at contraction hierarchy.
To me, ordering and contracting node looks impossible because when contracting a node, then it influence the other node. Therefore, it ...
0
votes
0answers
28 views
How to modify the following Dijkstra/ Uniform-cost search to return the result for all end points?
I know there is a lot of code out there that does this, but in particular, I'm trying to modify the following code to not just return the goal node/ one end point, but all endpoints. How do I go about ...
0
votes
0answers
42 views
Solving shortest path problem with Dijkstra’s algorithm for n negative-weight edges and no negative-weight cycle
Although many texts state Dijkstra's algorithm does not work for negative-weight edges, the modification of Dijkstra's algorithm can. Here is the algorithm to solve a single negative-weight edge ...
0
votes
0answers
73 views
Find every path that passes through certain edges
I'm faced with the following problem:
Given
Directed and unweighted graph, where each edge E has two attributes
Goal
Find every path through the 3 (or more) given edges in a specific order
...
0
votes
0answers
13 views
Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's “Discrete Mathematics and its Application”
I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places ...
0
votes
0answers
28 views
Is It Of Much Practical Use To Actually Use Fibonacci Heap Over Min Heap In Dijkstra Algorithm?
I know that to get the best technical running time in Dijkstra's shortest path algorithms, using a Fibonacci Heap is the correct way to go. However, the internet and in CLRS state that Fibonacci Heap ...
0
votes
2answers
330 views
CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm
I'm trying to better understand Question 24.3-4 From CLRS below:
Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm.
The program produces $v.d$ and $v.\pi$ for ...
-4
votes
0answers
35 views
Which heap to use when implementing Dijkstra's algorithm
Dijkstra's algorithm employs a heap. For which $m$ (as a function of $n$) can we choose $d$ so that $d$-heaps outperform Fibonacci heaps? Here $n$ is the number of vertices, $m$ is the number of edges,...
