Questions tagged [dijkstras-algorithm]
Algorithm for solving the single-source shortest-path problem in non-negatively weighted directed graphs
72 questions
0
votes
1
answer
57
views
Find path that minimizes the probability of a given event occurring, given the event occurs with a given probability per meter of movement
The task
Given the following conditions
a square area of side $L$ is given, say with the lower-left vertex in $(0, 0)$ and upper-right vertex in $(L, L)$,
$S = (L/2, 0)$ is the starting point of the ...
- 137
1
vote
1
answer
172
views
First n Super Ugly Numbers Algorithm and Proof
In the first n super ugly numbers problem we are given a list $P$ of primes. A super ugly number is either composite, i.e. the product of two or more primes, or is prime or equal to $1$. We are asked ...
- 71
1
vote
0
answers
76
views
Why doesn't dijkstra work for max weight edge path?
For a graph with no negative edge, let the length of a path be the max edge weight along the path. I checked the reasoning of Dijkstra carefully with this version, and can't find any errors, the logic ...
- 119
3
votes
1
answer
96
views
Other vertices on the shortest path between two specific vertices
I have been trying to solve a question that says in a directed graph with n vertices and m edges whose weights are all positive integers, we have specified two of them, namely $a$ and $b$. We want to ...
- 35
0
votes
0
answers
81
views
Dijkstra's algorithm where some vertices have only one path
Is there a way to use Dijkstra's algorithm in a graph with some points having only one connection? E.g. subway lines? I tried creating one but it fails if there's more than one line.
I'm trying to ...
- 21
1
vote
0
answers
45
views
Is it possible to start a Dijkstra search from a source node s, bounded at r, with a non-empty distance map and priority queue?
TL:DR: I want to know whether correctness is affected if I start Dijkstra with a distances map that already contains shortest paths shorter than $r$ and a priority queue initialised with those ...
- 11
1
vote
2
answers
264
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
3
votes
1
answer
167
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 ...
- 374
0
votes
1
answer
82
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
1
vote
1
answer
233
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 ...
- 341
0
votes
1
answer
148
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$...
- 67
0
votes
0
answers
72
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
4
votes
2
answers
477
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
0
votes
1
answer
204
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 ...
1
vote
1
answer
188
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 ...
- 57