Questions tagged [shortest-path]
The shortest-path tag has no usage guidance.
18
questions with no upvoted or accepted answers
32
votes
0
answers
6k
views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
(...
- 6,685
19
votes
0
answers
1k
views
Lower bounds on single-source shortest paths in directed graphs
Are there any non-trivial lower bounds on the complexity of single-source shortest paths (SSSP) in a directed graph, where all edges have non-negative edge weights? Can we rule out the possibility of ...
- 11.7k
11
votes
1
answer
519
views
Recent progress on the next-to-shortest-path problem for directed graphs?
In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem:
Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in ...
- 211
8
votes
0
answers
161
views
Is APSP verification easier than APSP?
In APSP, the input is an $n$-node directed weighted graph $G$, and the output is an $n \times n$ matrix holding pairwise shortest path distances between nodes in $G$. Define "APSP-Verification" as ...
- 2,393
4
votes
0
answers
1k
views
Path finding algorithm to maximise points of interest along the route
I am trying to write an algorithm to find a path (not the shortest one) between a given start and end point.
An user will enter the start location, the end location and the available time to travel. ...
4
votes
0
answers
510
views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
- 141
4
votes
0
answers
665
views
What about apply maxplus algebra for all-pairs shortest paths?
I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know ...
3
votes
0
answers
162
views
Multi-Agent Pathfinding
Quoting from Wang and Botea 2011:
An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each unit $...
- 1,132
3
votes
0
answers
648
views
A constrained shortest path problem. What is the complexity?
I've got the following problem:
Consider a graph $G=(V,E)$ with $V=\{v_1,\ldots,v_n\}$, and edge-set $E=\{e_1,\ldots,e_m\}$, with associated costs $c_1,\ldots,c_m$. The problem is to find the ...
- 39
2
votes
0
answers
619
views
Path finding on graph with state dependent edge costs
I'm looking for a version of path planning that is able to find paths in a graph where edge costs depend on the state of the moving entity. In such cases, it is required to also consider trade-offs, i....
- 161
2
votes
0
answers
612
views
Shortest non-crossing geometric paths
I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so ...
user7329
1
vote
0
answers
69
views
How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?
I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
- 119
1
vote
0
answers
118
views
multi-agent pickup and delivery algorithm and conflict resolution
I am looking for a pathfinding algorithm handling the following issues:
multiple agents
the computed paths for agents may not lead to collisions or deadlocks in space-time
a stream of activities
...
- 11
1
vote
0
answers
84
views
In a shortest path between two nodes, find if a certain node is unique
So my exact problem is, I have to find if there is any node which is unique in a shortest path. For example, in a square, any node is in the shortest path between any two adjacent nodes,but it is not ...
1
vote
0
answers
148
views
What are the differences between Theta* and Field D*?
Both Theta* and Field D* are variations on the A* algorithm, but are adapted for any-angle pathfinding rather than pathfinding constrained to a grid. The primary difference between these two ...
- 119
1
vote
0
answers
194
views
Dynamic k-shortest paths in a weighted transducer
I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly.
In this scenario ...
- 433
0
votes
0
answers
248
views
Efficiently computing propagation values for only a few positions in a grid
Consider a matrix filled with some nodes containing positive integers ("starts"), some nodes marked as a wall, and the rest of the nodes given a value of infinity.
The propogation rule is simple: For ...
- 1,132
0
votes
0
answers
162
views
Distance oracles in trees
Given an unweighted tree $T=(V,E)$ what is the minimum number of distance oracles that allow to detect the position in the graph of every node $v$?
A distance oracle is "special node" $u$ of the ...
- 221