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
2
votes
2answers
1k views

How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by ...
1
vote
2answers
84 views

Dijkstra's algorithm in a weighted graph

The Dijkstra's algorithm is never used for a graph with a negative weight. The following graph has negative weight but when the Dijkstra's single source shortest path algorithm run from vertex a, it ...
0
votes
1answer
47 views

M + N log N running time for Dijkstra

I'm taking the Design and Algorithms Part -II course in Coursera by professor Tim Roughgarden. In one of the classes, he mentioned that the running time for Dijkstra is $O(m \log n )$ using the heap ...
0
votes
1answer
31 views

Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three [duplicate]

Question: Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three in a graph with natural weights of the edges. My instructor has given me a hint ...
1
vote
1answer
17 views

Algorithm for shorthest path that contains exactly n edges of weight 2 in 1,2-weighted directed graph

I am trying to find an efficient algorithm for the following problem: Input: weighted directed graph G=(V, E) in which all edges are weigthed either 1 or 2 s,t ∈ V n ∈ N Output shortest path from s ...
1
vote
0answers
32 views

Which algorithms exhibits Greedy Choice Property but not Optimal Substructure Property

After a few courses using CLRS, I still have not been able to find a satisfying answer to the title question. This answer suggests Hoffman trees. But here the greedy choice is the two subtrees with ...
5
votes
1answer
769 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
77 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
34 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
29 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
45 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
189 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
48 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
805 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
43 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
118 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
15 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 ...
2
votes
1answer
155 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
337 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
734 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
358 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
378 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
773 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
123 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
56 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
14 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
443 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
106 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
452 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
738 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
279 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
641 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 ...