Skip to main content

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
1 vote
2 answers
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 ...
Sgg8's user avatar
  • 111
3 votes
1 answer
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 ...
Mařík Savenko's user avatar
0 votes
1 answer
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 ...
Eddie's user avatar
  • 1
1 vote
1 answer
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 ...
Daniel's user avatar
  • 83
0 votes
1 answer
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$...
vhd's user avatar
  • 45
0 votes
0 answers
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 ...
Andrew's user avatar
  • 286
4 votes
2 answers
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 ...
Daniel's user avatar
  • 149
0 votes
1 answer
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 ...
ViktorMaksimoski's user avatar
0 votes
1 answer
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 ...
Hjm's user avatar
  • 47
0 votes
1 answer
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 ...
nat.d's user avatar
  • 1
0 votes
1 answer
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 ...
Amir's user avatar
  • 1
0 votes
2 answers
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 ...
Mike's user avatar
  • 33
0 votes
2 answers
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 ...
ant0982's user avatar
  • 13
2 votes
1 answer
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 ...
Dmitry's user avatar
  • 345
0 votes
1 answer
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 ...
Rasmus IN's user avatar
0 votes
0 answers
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{|...
Freddy Mcloughlan's user avatar
1 vote
1 answer
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 ...
PythonAddict's user avatar
2 votes
0 answers
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 ...
cuneyttyler's user avatar
6 votes
1 answer
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 ...
Rohit Pandey's user avatar
1 vote
0 answers
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, ...
nick shetty's user avatar
0 votes
0 answers
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 ...
csstudent3423's user avatar
1 vote
1 answer
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 ...
Mohamad S.'s user avatar
1 vote
0 answers
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 ...
Sneftel's user avatar
  • 221
0 votes
0 answers
679 views

Number of shortest paths between two nodes in undirected unweighted graph

I'm trying to devise a $O(|V| + |E|)$ algorithm to calculate number of shortest paths between $s$ and $f$ on a undirected, unweighted graph. Can someone please check my pseudo-code? Also, isn't $O(|V| ...
chesslad's user avatar
  • 113
1 vote
1 answer
1k views

Given a source and destination, find the path with minimum stress level in a Graph

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
KnownUnknown's user avatar
2 votes
1 answer
721 views

Dijkstra's Algorithm Same Node Added Multiple Times to Priority Queue

In the this discussion of Dijkstra's Algorithm appear the following comments: ...
Robin Andrews's user avatar
2 votes
1 answer
629 views

Shortest path with forced intermediate nodes

I have a directed graph with roughly 2000 nodes, and roughly 4000 edges. I have created an application so the people that use it can easily see the path drawn on a map, if they e.g. want to find the ...
Denver Dang's user avatar
3 votes
3 answers
3k views

Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?

Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V ...
Meowser's user avatar
  • 33
0 votes
0 answers
268 views

dijkstra with adjacency list and minimum heap as queue vs adjacency matrix and a normal array as "queue"

Which one should be faster? I have written a script comparing both run time, initially the implementation with adjacency list and minimum heap performs faster, but as the number of nodes/edges ...
xineta5158's user avatar
-1 votes
1 answer
79 views

Dijkstra Algorithm

I have couple of questions about Dijkstra algorithm Can the algorithm work if there are negative weights at the starting point? Can we make the algorithm work with negative weights if we add a long ...
Thanos's user avatar
  • 1
2 votes
2 answers
2k views

Can you use Dijkstra's algorithm to find the maximum cost path?

Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree. Is it possible to negate all ...
David's user avatar
  • 121
6 votes
5 answers
3k views

Example of a graph with negative weighed edges in which Dijkstra's algorithm does work

I was asked to give an example of a graph that has edges with negative weight, but Dijkstra's algorithm will still give us the correct output. It was part of a prove/disprove question. The claim was.. ...
Yonatan Lozinsky's user avatar
0 votes
0 answers
141 views

A relaxation-free variant of Dijkstra's shortest path algorithm

I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
nalzok's user avatar
  • 1,101
2 votes
2 answers
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 ...
Jarne Renders's user avatar
1 vote
2 answers
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 ...
kiv's user avatar
  • 339
0 votes
1 answer
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 ...
Veera Kumar's user avatar
0 votes
1 answer
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 ...
Zara Levin's user avatar
1 vote
1 answer
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 ...
Andrew Brenner's user avatar
2 votes
0 answers
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 ...
user avatar
6 votes
1 answer
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 ...
M G's user avatar
  • 65
2 votes
1 answer
640 views

Dijkstra's Algorithm Invariant

I am trying to prove the first assertion in the following code, taken from notes of Damon Wischik: ...
Jeremy Yeo's user avatar
-1 votes
1 answer
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 ...
pinky_dinky_doo400's user avatar
0 votes
0 answers
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 ...
user11452926's user avatar
2 votes
1 answer
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 ...
Andre's user avatar
  • 21
1 vote
2 answers
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 ...
Exzone's user avatar
  • 235
1 vote
0 answers
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 ...
errorcodemonkey's user avatar
0 votes
1 answer
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 ...
sarthak tripathi's user avatar
2 votes
0 answers
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 ...
Anton Ballmaier's user avatar
0 votes
0 answers
269 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 ...
Thomas Pellegrini's user avatar
0 votes
0 answers
35 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 ...
Abhishek Ghosh's user avatar