Questions tagged [dijkstras-algorithm]

The tag has no usage guidance.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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,...