# Questions tagged [dijkstras-algorithm]

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

66 questions
Filter by
Sorted by
Tagged with
1 vote
41 views

### Shortest path between two nodes with time-dependent edge weights

I have city traffic data. The roads are represented as a directed graph (a road can have traffic both ways, at most two-lane roads included), vertices being points on a map where two or more road ...
• 111
88 views

### The existence of a (nearly) quadratic time algorithm for 2-steps shortest path or smallest triangle

I am interested in two problems, which seem to be related, solving each will advance me in other possible directions. In both problems, $G=(V,E)$ is a positively-weighted undirected graph. Denote its ...
31 views

### Lightest Paths Tree that is 10 times heavier than an MST of the same graph

Something I was asked to solve and tried to come up with a formula or some method to solve it after I did and couldn't. Given is a graph G=(V,E) that is undirected and weighted. Say we want to find ...
1 vote
86 views

### Disconnection of a directed and weighted graph

Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive. In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$. The question asks to find a ...
• 83
50 views

### supplying water for all houses of a city with either a well or pipe

Consider $n$ houses in a city which each house's water can be supplied with either a well or pipes from other houses. Constructing a well in a house $i$ costs $w_i$ and connecting a pipe from house $i$...
• 45
39 views

### Running time of variant of Dijkstra's algorithm

Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
• 286
260 views

### Single Source Shortest Path Problem with Multiple Weights Each Edge

I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p ...
• 149
123 views

### How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford

I want to find how many shortest paths are there from Node A to node B. For example, let's say we have a graph with 3 nodes and 3 connections: from 1 to 2 weight 5 from 1 to 3 weight 11 from 2 to 3 ...
112 views

### Minimum number of skips needed for shortest path

In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $\leq W$. In our given graph there is no such path but we have the ...
• 47
87 views

### Dijkstra's shortest path algorithm

I am reading about algorithms to find the shortest path on a graph with one source, and I have a doubt about Dijkstra's algorithm about the negative weights on edges. In this case is Bellman-Ford ...
119 views

### find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)

We have a weighted and undirected graph. I want to find the shortest path between two vertices with Dijkstra algorithm. But in the path, the weight of the edges should be increased and decreased one ...
• 1
306 views

### Proof showing when Dijkstra’s algorithm fails for negative edge weights

How do I show the correctness proof of Dijkstra’s algorithm for negative edge weight $\textbf{indicating the point in the proof where it breaks or does not hold}?$ I tried proving it like this, but i ...
• 33
177 views

### subtract the weight of the largest edge

I have an oriented and weighted graph, and I need to find the cheapest route from source to destination. Now I have a source node A and a destination node B the cheapest path is given to me by the sum ...
• 13
489 views

### Dijkstra as a greedy algorithm

I'm preparing some material for students about greedy algorithms, and there is one point that confuses me: how Dijkstra's algorithm fits into the greedy framework. I would like to say that we have ...
• 345
500 views

### Does order of elements in a set matter in Dijkstra's Algorithm?

When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
45 views

### Dijkstra's runtime analysis in terms of $|V|$ and $|E|$

I'm unsure as to the amount of operations in Dijkstra's shortest path in terms of $|V|$ and $|E|$. My guess is that there are (worst case - complete graph): |V| + \sum^{|V|}_{i=1}{(|V|-i)} = \frac{|...
1 vote
178 views

### Shortest path in a directed weighted graph

Suppose we have a directed, weighted graph, $G = (V, E, w)$, with non-negative weights. We define the weight of the shortest path different from the original definition. The weight of a path with at ...
557 views

### Is there an efficient algorithm for calculating shortest path for multiple (source,target) pairs in a graph?

I wonder if there is an algorithm which takes multiple (source,target) pairs and a max_depth parameter and returns all or some of the paths found with those pairs? Thinking of Dijkstra's algorithm, it ...
• 121
590 views

### What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?

I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from Introduction to Algorithms by Cormen et al. The $w$ parameter is the weight function such ...
• 377
1 vote
81 views

### compute shortest distance to a different sink

Given a directed graph G=(V, E) and a sink vertex t. Edge costs may be negative, zero, or positive. consider d(v) contains the length of the shortest path from v to t Given a new sink t2 in the graph, ...
345 views

### bellman ford and dijkstra sparse vs dense graphs

I believe using big o notation that Bellman-Ford is to be expected to be faster on sparse graphs and dijkstra's should be expected to be faster on dense graphs, but in practice dijkstra's is always ...
1 vote
430 views

### How to find the lightest path that has at least one vertex of each color?

I've faced this question in my homework. In a graph $G=(V,\ E)$ where every $v\in V$ has a color, a colored path is a path such that it has at least one vertex of each color. We're given a directed ...
• 449
1 vote
30 views

### Node domination in constrained path search

It's possible to modify a graph search algorithm such as Dijkstra's or A* to allow for non-additive objectives or constraints. Is there a standard treatment for these algorithms to reduce unnecessary ...
• 221
679 views

• 1,101
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
599 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 ...
• 339
2k 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 ...
122 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 ...
• 101
1 vote
24 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 ...
121 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 ...
1k 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 ...
• 65
640 views

### Dijkstra's Algorithm Invariant

I am trying to prove the first assertion in the following code, taken from notes of Damon Wischik: ...
175 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 ...
92 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 ...
• 101
256 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 ...
• 21
1 vote
733 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 ...
• 235
1 vote
136 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 ...
3k 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 ...
148 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 ...