Skip to main content

Questions tagged [dijkstras-algorithm]

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

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
0 answers
494 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
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
2 votes
0 answers
147 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
2 votes
0 answers
204 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 ...
Mahdaoui7's user avatar
1 vote
0 answers
77 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
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
1 vote
0 answers
132 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
1 vote
0 answers
131 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 ...
Andy's user avatar
  • 141
1 vote
0 answers
54 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 ...
nimdrak's user avatar
  • 111
0 votes
1 answer
30 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
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
0 votes
1 answer
109 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
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
0 votes
0 answers
331 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
0 votes
0 answers
658 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
0 votes
0 answers
261 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
0 votes
0 answers
137 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
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
0 votes
0 answers
266 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
34 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