Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
642
questions
1
vote
0
answers
94
views
Question about step in proof that predecessor subgraph forms a breadth-first tree
Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:
Theorem 22.5: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, ...
- 33
1
vote
0
answers
43
views
How to compute the updated shortest paths given a set of edge insertions efficiently?
Let $G = (V, E)$ be a graph with edge weights $w: E \rightarrow \mathbb{R} \cup \{\infty\}$.
Let $P := \{(a_i, b_i, w_i)\}$ be a set of tuples of nodes $a_i, b_i \in V$ with shortest distance $w_i$ ...
0
votes
0
answers
35
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 ...
- 287
1
vote
1
answer
53
views
Solving shortest path with negative weights with linear program. What is the underlying problem we want to solve?
Let us consider a shortest path problem with weights $w_e$ for each edge $e$. It can be formulated as a (integer) linear program (ILP).
\begin{align}
\min \quad &\sum_{e \in E} w_e x_e \\
s.t. \...
- 13
1
vote
1
answer
53
views
Finding shortest path between two points in a polygon whose vertices are given?
A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
- 512
0
votes
0
answers
19
views
k-shortest paths with iso-timing constraint
I would like to solve the $k$ shortest paths on a directed graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$ :
\begin{equation}
\label{eq:1}
\underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\sum_{(i,j)\in\...
- 51
0
votes
1
answer
39
views
Shortest path problem with multiple objectives
I would like to solve a shortest path problem on a graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$, which comes to minimize :
\begin{equation}
\label{eq:1}
\underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\...
- 51
4
votes
2
answers
61
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
0
answers
17
views
Importance of an edge regarding distances
Given a graph $G=(V,E)$ and any edge $(u,v) \in E$, let us denote by $G_{(u,v)}=(V,E\setminus\{(u,v)\})$ obtained from $G$ by removing this edge.
I am interested in the difference between the average ...
- 623
2
votes
0
answers
16
views
Inverted Min Cost Max Flow
I'm starting to think there's no possible solution to this problem, but before jumping to conclusions I want to confirm it with collective knowledge.
Let's imagine that there's a 2D grid, where S ...
0
votes
0
answers
31
views
Finding Minimum Elements for Longest Path in Disjoint Set
I want to know the minimum number of elements needed to create a tree with the longest path having n edges. How can I approach this problem using the forest implementation of disjoint sets with union ...
1
vote
0
answers
31
views
Is Dijkstra's algorithm used in cheapest airfare calculators?
Is Dijkstra's shortest-path graph algorithm used in cheapest airfare calculators like Expedia or CheapAir?
- 146
1
vote
0
answers
57
views
Finding the shortest path with Bellman-Ford [duplicate]
I feel this is a basic question but have been stuck at this for days. Consider an undirected graph with positive weights on its edges. The goal is to find is to get the shortest path between any two ...
- 257
1
vote
1
answer
22
views
Route planning on line segments which can be connected or not
I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am ...
- 111
0
votes
1
answer
83
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 ...
- 37
1
vote
1
answer
129
views
Solution for the path-finding problem which visits multiple sequences of nodes
Summary
Recently I have had a path-finding puzzle that has some complex constraints (currently, I don't have any solution for this one)
A 2D matrix represented the graph. The length of a path is the ...
- 11
1
vote
0
answers
83
views
Successive shortest paths with fixed costs and costs per unit
I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
- 111
0
votes
1
answer
74
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 ...
- 1
0
votes
1
answer
73
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
0
votes
0
answers
26
views
3-Colored Edges cheapest path [duplicate]
Given a directed graph $G$ with weights on it's edges (weights $\in \mathbb{R}$) where all edges are colored $R,G$ or $B$
Find an algorithm to find cheapest path that starts in $s\in V$ and ends at $t\...
- 315
1
vote
2
answers
64
views
Shortest path algorithm on graphs with non-numerical weights
TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of ...
0
votes
1
answer
67
views
Intuition of Flod-Warshall shortest path algorithm
I try to wrap my head around the Floyd-Warshall algorithm, and I don't understand why the shortest path is guaranteed to be found since we check only the alternative connections up to one hop deep.
...
- 103
0
votes
1
answer
71
views
The solution for the all-pair shortest path problem on unweighted and undirected graph
The multi-source shortest path problem for unweighted and undirected graph is as follows: Given an unweighted and undirected graph, find the length of the shortest path between any pair of vertexes.
A ...
- 69
0
votes
2
answers
174
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
1
vote
1
answer
67
views
The length of the shortest $s$-$t$ path equals the maximum tension between $s$ and $t$
I am stuck at the following exercise:
Consider a directed graph $G = (V, A)$ with start vertex $s ∈ V$, target vertex $t \in V$ and weights $w_{ij} \in \mathbb{R}$ for each arc $(i, j)\in A$. For any ...
- 457
0
votes
0
answers
28
views
What's the average and worst-case time complexities of the following BFS for finding shortest paths?
Dijkstra's algorithm is the go-to method for finding the shortest path lengths between a source node and all the other nodes in a directed graph with nonnegative edge weights. I am wondering how ...
- 123
1
vote
1
answer
152
views
find shortest path from single source to multiple destinations with obstacles which you can move
a formulation on an example:
let's have on a grid:
a position of a bee queen Q (source node),
a set of positions of free cells to lay an egg E (destination nodes),
and a set of positions with worker ...
- 111
0
votes
1
answer
74
views
Implementation check for Kruskal's algorithm used for maze generation
I have a pathfinding project and I want to use Kruskal's algorithm as a maze generator. I am using a rank-based disjoint set data structure to detect cycles, which seems to be the standard way.
...
0
votes
1
answer
263
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 ...
0
votes
2
answers
302
views
Calculate shortest cycle that contains node $s$
Let $ G(V,E,w)$ be a graph with no negative weights.
Describe an algorithm that returns the shortest cycle containing a node $ v $.
I came across this algorithm https://courses.engr.illinois.edu/cs374/...
- 232
1
vote
1
answer
168
views
Algorithm to compute cheapest path between two pixels in an image
I need to compute the cheapest path between two pixels in an image. The travel cost is specified by the user, and may depend on the distance between the pixels (including pixel values, which is ...
- 147
0
votes
1
answer
192
views
Any-goal bidirectional A* pathfinding reference
I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that ...
- 121
1
vote
1
answer
82
views
Correctness of bft resulting in shortest path
I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path:
source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf
The ...
- 47
0
votes
2
answers
327
views
Find a simple path from S to T in a directed graph so that the product of its weights is maximum
I'm looking for an algorithm that finds a simple path from S to T in a directed graph (which might have cycles) so that the product of edge weights in the path is maximum. All the edge weights of the ...
- 133
2
votes
0
answers
175
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
2
votes
1
answer
583
views
Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?
The problem concerns finding shortest paths in graph from a single source to a single destination.
So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
0
votes
1
answer
287
views
Is there an edge whose removal will extend the shortest path? - graph problem
Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal ...
- 71
1
vote
1
answer
133
views
Subpath optimality lemma in weighted undirected graphs
In an introductory course on Dijkstra's algorithm, I enunciated the following lemma :
Let x →* z be a shortest path in a weighted graph and let y be any vertex along that path. It follows that x →* y ...
- 233
0
votes
1
answer
240
views
why use bellman-ford instead of Dijstra in RIP routing?
The RIP routing protocol was published in 1988 and uses Bellman-Ford algorithm to calculate shortest path. Also more recent version of RIP (RIPv2 and RIPng) use the same algorithm. The Djikstra ...
- 103
6
votes
1
answer
495
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 ...
- 305
1
vote
0
answers
67
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, ...
0
votes
0
answers
36
views
Updating Shortest Path Weight from One Destination to Another
Let $G=(V,E)$ be a directed graph with possibly negative edge weights. Given a destination $t$. Suppose that we have already known $d_v$, the shortest path weight from $v$ to $t$. If I'd like to ...
- 121
1
vote
0
answers
38
views
Shortest path with vertex capacity
I have an undirected graph where each edge $e=\{u,v\}$ has a positive weight $w_{uv}$ and each vertex $v$ has a positive capacity $c_v$. There are two special vertices: a source vertex $s$ and a ...
- 1,046
1
vote
0
answers
114
views
Min weighted path in a graph, but you could die
The min-path problem is mostly motivated by a graph with cities as vertices and roads between them as edges. Each edge has a weight which could be the length of the road or the time it takes to cross ...
- 305
1
vote
1
answer
479
views
extending bellman ford to find shortest weight paths with no repeating vertices
Is it possible to extend the Bellman Ford algorithm to output all shortest simple paths without repeating vertices?
The issue is that the Bellman Ford algorithm doesn't make any checks for whether the ...
- 289
2
votes
1
answer
270
views
The distinct-vertex $\alpha$-edge variant of the all-pairs shortest paths problem
The following problem is a variant of the all pairs shortest path problem: Given a weighted, directed graph $G=(V,E), |V| = n,|E| = m,$ and an integer $\alpha\ge 1$, how can I find an efficient ...
- 289
3
votes
1
answer
87
views
Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph
Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting ...
- 289
0
votes
1
answer
64
views
Bellman Ford may not update distance correctly by termination?
Consider the example shown in the above figure. Let's consider two orders (1) S, A, B and (2) S, B, A for traversing the graph and updating the distance d (numbers in circle are distance d):
1- start ...
1
vote
1
answer
379
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 ...
- 453
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 ...
- 221