Questions tagged [dijkstras-algorithm]

Algorithm for solving the single-source shortest-path problem in non-negatively weighted directed graphs

Filter by
Sorted by
Tagged with
5
votes
1answer
607 views

Dijkstra's algorithm vs A*

The A* algorithm terminates when the f (distance + heuristic) is less than the f values for all of the nodes that haven't been visited. Dijkstra's algorithm produces the shortest path to every node ...
2
votes
1answer
56 views

Dijkstra's Algorithm Invariant

I am trying to prove the first assertion in the following code, taken from notes of Damon Wischik: ...
-1
votes
1answer
33 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 ...
2
votes
1answer
37 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 ...
1
vote
2answers
142 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 ...
0
votes
0answers
44 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
1answer
612 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 ...
2
votes
0answers
38 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
87 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
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
152 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
274 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
685 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
1answer
263 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
1answer
282 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 ...
2
votes
1answer
663 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
107 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
117 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
53 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
11 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
384 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 ...
0
votes
2answers
102 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
415 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
642 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
253 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 ...
4
votes
1answer
560 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 ...