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
628 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 ...
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 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 ...
213 views

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 ...
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 ...
195 views

### Anyone recognize this as a special type of multi-commodity flow problem?

Consider this problem:  \begin{align} \min_{y,z,l \geq 0} \quad & g(y,z,l) := \sum_{(i,j)\in E} \sum_p (-w_{ijp}) y_{ijp} & \\ \textrm{s.t.} \quad & \left( \sum_{(i,j)\in E} y_{ijp} + ...
516 views

### What is the proof that visibility graphs can be used to compute the shortest path?

I am trying to understand what the proof is that constructing a visibility graph and searching on can give you the shortest path between two points, avoiding a set of convex polygons. I am trying ...
1k views

### Shortest distance problem with length as functions of time

Motivation The other day, I was travelling around the city with public transport and I made up an interesting graph problem modelling the problem of finding the shortest-time connection between two ...
1 vote