Share Your Experience: Take the 2024 Developer Survey

Questions tagged [shortest-path]

The tag has no usage guidance.

81 questions
Filter by
Sorted by
Tagged with
82 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
• 1,019
1 vote
62 views

Shorter than target vector path algorithm

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
• 1,019
213 views

• 241
1 vote
119 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
121 views

Multiple source shortest path with one reversal [closed]

Lets say we have a directed graph G, with vertices V, that have lengths l. I need to find the shortest path between every ordered pair of vertices in the graph, with the following constraint: In a ...
1 vote
139 views

• 131
1 vote
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 ...
2k views

Finding the two shortest paths while minimizing the number of nearby/common edges

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary. Consider the following variant: ...
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 ...
• 12.1k
360 views

Ref question: K-nearest neighbours in a graph

Given an undirected graph $G$ with $n$ vertices, $m$ edges, and positive weights on the edges, I am interested in the problem of computing for each vertex the $k$ distinct vertices in $G$ that are ...
• 9,626
781 views

Highway dimension

I'm interested in understanding some recent theoretical results on pathfinding. Specifically this paper: http://research.microsoft.com/apps/pubs/default.aspx?id=201061 I understand from the paper ...
• 21
3k views

Shortest path hitting a given vertex

I believe this problem to be NP-Complete, but I'm unable to find any references on possible reductions. Given a weighted graph (either undirected or directed, I cannot find results for either but am ...
251 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
1k views

• 221