Questions tagged [dijkstras-algorithm]
The dijkstras-algorithm tag has no usage guidance.
29
questions
-1
votes
1answer
30 views
UCS and Dijkstra's algorithm do both of them give the minimal cost between two vertices?
i tried both algorithm to find the shortest path with minimal cost between two vertices,but most of the time Dijkstra gives a different path and the cost is smaller than the cost for the path UCS ...
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 ...
-3
votes
0answers
12 views
Asymptotic growth rate - Dijkstra [closed]
Recall that Dijkstra’s algorithm, using a priority queue, does n Extract-Min operations and at
most m Decrease-Key operations. In a d-ary heap (d-heap) with at most n items, the number
of comparisons ...
-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,...
0
votes
1answer
210 views
find shortest paths from source to all vertices using Dijkstra’s Algorithm?
For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ???
For ...
0
votes
2answers
331 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
1answer
495 views
Dijkstra without decrease key
I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new ...
1
vote
2answers
123 views
Minimum distance in an undirected weighted graph to cover k nodes using teleportations
I have been practicing problems on graphs and shortest paths and
I encountered a problem that I'm struggling to understand.
Can you give me any tips and/or can you confirm that I got the general
...
2
votes
1answer
35 views
shortest path in color-weighted graphs
I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum ...
0
votes
1answer
499 views
Why is DFS not suited for shortest path problem?
I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know ...
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 ...
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 ...
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
1answer
207 views
Create an algorithm for computing the shortest path in O(m + nlogn)
So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non ...
0
votes
0answers
34 views
Algorithm to calculate shortest path when updating the heaviest edge in a path [duplicate]
For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge.
$$w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...
2
votes
1answer
149 views
Modified shortest path problem
For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{...
1
vote
2answers
224 views
Analysis of Dijkstra algorithm's (Lazy) running time
I'm trying to figure out the running time for a Dijkstra algorithm. All the sources I have read say that the running time is O(E * log (E)) for a lazy implementation.
But when we do the math we get ...
3
votes
2answers
661 views
Find the shortest path that goes through an even number of red edges
I'm looking for an algorithm for the problem:
"Given an undirected graph with positive weights on its edges and some of the edges are red and some are blue. Describe an algorithm that finds the ...
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 ...
2
votes
1answer
626 views
Gas Station Problem - Dijkstra's Algorithm variation
I am trying to find an algorithm which finds the least expensive route from one town to another.
This is the general setup.
There are a series of one-way roads from some towns to other towns. Not ...
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 ...
3
votes
1answer
105 views
Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same
Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all ...
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
2answers
95 views
“Subpaths” of Dijkstra's shortest path also shortest?
I have trouble putting this into formal mathematical terms, so let's suppose that I found the shortest path from A to E as A > C > D > B > F > E with Dijkstra's algorithm. Am I correct in assuming ...
0
votes
1answer
380 views
Dijkstra's algorithm - Finding additional paths with same weight but different edges
given a network with n stations. assuming the shortest between s,t was found using dijkstra's algorithm. let that path be denoted as $(a_1,a_2,...,a_k)$
assume that between the nodes s and t, there's ...
1
vote
2answers
579 views
Dijkstra and A* Algorithms: Why is A* faster?
I am learning about Dijkstra's Algorithm and the A* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A* Algorithm is faster ...
3
votes
2answers
226 views
Why doesn't Dijkstra's use a shortest-path first search?
When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we ...
BlueRaja - Danny Pflughoeft
1,3881 gold badge9 silver badges14 bronze badges
