Questions tagged [shortest-path]

The tag has no usage guidance.

19 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
32
votes
0answers
5k 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\}$. (...
18
votes
0answers
922 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 ...
10
votes
1answer
333 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 ...
8
votes
0answers
135 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 ...
4
votes
0answers
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
0answers
471 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 ...
4
votes
0answers
646 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
0answers
157 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 $...
3
votes
0answers
634 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 ...
2
votes
0answers
560 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....
2
votes
0answers
553 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 ...
1
vote
0answers
109 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 ...
1
vote
0answers
82 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
0answers
131 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 ...
1
vote
0answers
192 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 ...
0
votes
0answers
49 views

Minimal lexicographical path on DAG in O(||V| + |E|)

Let's assume, that we have directed asyclic graph and nodes U and V. Every edge of this graph is marked with alphabet letter (alphabet size is fixed). Is there any way to answer, what is the shortest ...
0
votes
0answers
28 views

Optimum first stage solution of two stage stochastic shortest path induces tree

I struggle with the proof of Lemma 1 in the Paper "Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems" by Ravi and Sinha and hope this is the right community ...
0
votes
0answers
211 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 ...
0
votes
0answers
146 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 ...