Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [shortest-path]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
106 votes
6 answers
54k views

How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

A lot of pathfinding algorithms have been developed in recent years which can calculate the best path in response to graph changes much faster than A* - what are they, and how do they differ? Are ...
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\}$. (...
Stasys's user avatar
  • 6,765
19 votes
2 answers
885 views

Axioms for Shortest Paths

Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences ...
ilyaraz's user avatar
  • 1,569
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 ...
D.W.'s user avatar
  • 12.1k
17 votes
2 answers
5k views

Finding k shortest Paths with Eppstein's Algorithm

I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap ...
Laura's user avatar
  • 273
16 votes
1 answer
15k views

Finding the shortest path in the presence of negative cycles

Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...
jleahy's user avatar
  • 263
13 votes
0 answers
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 ...
user514014's user avatar
12 votes
2 answers
832 views

Graph classes for which the diameter can be computed in linear time

Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) ...
Juho's user avatar
  • 3,170
12 votes
3 answers
2k views

Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

Quite similar to my previously posted question. This time however, the graph is undirected. Given An undirected graph $G$ with no multiple-edges or loops, A source vertex $s$, A target vertex $t$, ...
Lior Kogan's user avatar
11 votes
1 answer
1k views

Identifying useless edges for shortest path

Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex $...
a3nm's user avatar
  • 9,419
10 votes
3 answers
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 ...
JS_'s user avatar
  • 373
8 votes
2 answers
550 views

Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
jutky's user avatar
  • 181
8 votes
1 answer
410 views

Motivation for Developing Shortest Path Simplex Algorithms

I'm reading Efficient Shortest Path Simplex Algorithms by Donald Goldfarb, Jianxiu Hao and Shen-Roan Kai who considered "the specialization of the primal simplex algorithm to the problem of finding a ...
Jozef's user avatar
  • 183
8 votes
2 answers
6k views

Finding a minimum "node" weight path

Suppose a graph with node weights only (no edge weights). For a given source-sink pair, how can I find a path with the minimal sum of node weights? Does this problem have a name? Is it possible to ...
Chang's user avatar
  • 253
8 votes
0 answers
168 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 ...
GMB's user avatar
  • 2,403
7 votes
1 answer
665 views

Shortest paths perturbation

I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that ...
Matteo's user avatar
  • 569
7 votes
3 answers
609 views

Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path

I'm trying to preprocess a very large and sparse directed graph in order to do faster shortest path searches. The vertices have no natural distance function, and the edges are unweighted. One ...
dacc's user avatar
  • 173
7 votes
2 answers
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 ...
Sariel Har-Peled's user avatar
6 votes
2 answers
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 ...
Matthew G Dippel's user avatar
6 votes
2 answers
2k views

In a resistor network, is there any relation between the shortest path and the maximum electric current path?

Consider a shortest path problem between the source $s$ and sink $t$ in an undirected weighted graph. There's a well known algorithm such as Dijkstra's algorithm that solves this problem. Naturally, ...
Federico Magallanez's user avatar
6 votes
1 answer
341 views

Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time

I'm working on a project centered around the All-Pairs Shortest Paths (APSP) problem. Common algorithms to APSP (Floyd-Warshall, Bellman-Ford, Johnson's) work with the standard definition of the ...
Koen's user avatar
  • 61
5 votes
3 answers
2k views

Dynamic programming and shortest path problem

Several months back, I asked in math.SE the following question I wonder if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source and ...
Tim's user avatar
  • 639
5 votes
2 answers
11k views

How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once. For a subset $S$ of nodes and a node $i\in S$, let $D[...
f10w's user avatar
  • 241
5 votes
2 answers
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: ...
Otto Nahmee's user avatar
5 votes
1 answer
134 views

Shortest path with affine updates and fixed dimension

One may look at the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with ...
user1868607's user avatar
  • 1,019
5 votes
1 answer
270 views

Max Sum Product Multi-objective Shortest path problem

Is anything known about the following problem: I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1. A path is first assigned a vector, ...
Nathanaël Fijalkow's user avatar
4 votes
1 answer
282 views

For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find $k$ disjoint paths between pairs of vertices $\{s_i,t_i\}_{i=1}^k$ in poly time for fixed $...
R B's user avatar
  • 9,458
4 votes
1 answer
260 views

Shortest distance/path between two households

If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently? Say you are considering the set of all ...
Derrek Whistle's user avatar
4 votes
1 answer
217 views

Shortest path property and monadic second order logic

I know that induced paths and Hamiltonian cycles can be expressed with monadic second-order logic ($MS_2$). Is it possible to express the shortest path in $MS_2$?
fva's user avatar
  • 45
4 votes
1 answer
343 views

Shortest path on a hypergraph with no leftovers

In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by ...
Craig Gidney's user avatar
  • 1,518
4 votes
1 answer
408 views

Dynamic all-pairs shortest paths - O(1) query

I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally: My primary focus is to achieve ...
Darmak's user avatar
  • 141
4 votes
1 answer
397 views

Finding shortest path while maximizing the number of overlapping 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: ...
Mojtaba's user avatar
  • 43
4 votes
1 answer
537 views

Minimum Union-Sum Cost Path

I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
mnmp's user avatar
  • 175
4 votes
1 answer
91 views

Cooperative Pathfinding to minimize global costs

There are some algorithms and methods around, that allow cooperative pathfinding. Unfortunately they all seem to aim at avoiding collisions or conflicts between entities. I'm looking for an algorithm ...
Stanley F.'s user avatar
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. ...
Radu-Stefan Zugravu's user avatar
4 votes
0 answers
514 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 ...
remo's user avatar
  • 141
4 votes
0 answers
666 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 ...
Immanuel Weihnachten's user avatar
3 votes
1 answer
219 views

Minimum offset while measuring TSP paths

I have Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I am trying to solve TSP with brute algorithm, and I want to ...
Ilya Gazman's user avatar
3 votes
1 answer
550 views

Breadth first search and Eppstein K shortest paths algorithm

I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf I have trouble particularly ...
zenperttu's user avatar
  • 133
3 votes
1 answer
738 views

What exactly is Lawler's modification to Yen's algorithm and how does it work?

I recently read about Yen's algorithm, I understand the algorithm and it seems correct, however Wikipedia mentions that there exists "Lawler's modification" to the algorithm, which is described as ...
Z2VCv's user avatar
  • 33
3 votes
1 answer
279 views

Proof of SPFA's worst-case complexity?

I am trying to prove the worst-case asymptotic time complexity of the Shortest Path Faster Algorithm (SPFA). I know the complexity is the same as the "original" Bellman-Ford (BF) algorithm, ...
Maltus's user avatar
  • 73
3 votes
1 answer
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 ...
saul.shanabrook's user avatar
3 votes
1 answer
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} + ...
user164151's user avatar
3 votes
1 answer
214 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{...
user3494047's user avatar
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 $...
Phylliida's user avatar
  • 1,132
3 votes
0 answers
653 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 ...
sjoerd999's user avatar
2 votes
1 answer
104 views

Constant Width Max Sum Product Multi-objective Shortest path problem

This question is a follow-up on the question I asked three days ago here. For convenience I restate it here. I am given a graph. Each edge is labelled by a vector of numbers, called weights. They ...
Nathanaël Fijalkow's user avatar
2 votes
1 answer
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 ...
Daniel's user avatar
  • 21
2 votes
1 answer
327 views

Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with ...
Christoph's user avatar
2 votes
1 answer
594 views

Maximum difference between two shortest paths

My problem is the following maximization problem: Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two ...
Florian K's user avatar