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
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 ...
0 votes
1 answer
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
1 answer
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 ...
0 votes
2 answers
213 views

Shortest path with permutations and fixed dimension

I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on $...
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 ...
1 vote
1 answer
83 views

Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
1 vote
0 answers
32 views

How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

Thanks for reading, let me provide the definitions first. A separator of a graph $G$ is a set of vertices $C$ such that removing $C$ cuts the graph into two disconnected parts $A, B$ such that they ...
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$?
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 ...
1 vote
1 answer
548 views

Does Dijkstra's algorithm run faster on a DAG?

I know that Dijkstra's algorithm generally runs in $O(E \log V)$ using a min-heap. And I know we can use dynamic programming to find the shortest path of a DAG in $O(V+E)$. However, I was wondering ...
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 ...
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 ...
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 ...
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 ...
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, ...
1 vote
0 answers
71 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 ...
-1 votes
1 answer
96 views

Multi agent path following with collision avoidance with pre-determined path

I am working on a multi-agent pathfinding algorithm. I am aware of other techniques, but planned on the folowing strategy only. The problem: There is 12x12 grid, with a few solid blockades within them....
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 ...
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 ...
8 votes
2 answers
550 views

Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
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 ...
1 vote
1 answer
447 views

Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

A walk in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. Note that a trial may visit a vertex multiple times ...
1 vote
1 answer
1k views

directed or bidirected in relation to mssp (Multiple source shortest path)

Firstly I wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or does it become bi-directed? The main question is i have a graph ...
1 vote
1 answer
5k views

Number of simple paths between two vertices in a DAG

Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$. My problem is: how many simple $s-t$...
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) ...
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 ...
0 votes
2 answers
115 views

Bellman-Ford with Non-edge-decomposable Path Weights

Consider a directed graph $G(V,E)$ with non-negative edge weights. Also, let us define the weight of a path as non-edge-decomposable, that is, the weight of a path cannot be written as the sum of a ...
-1 votes
1 answer
172 views

When is extra vertex required in arbitrage detection using Bellman Ford?

I am studying applications of shortest path, in particular arbitrage. Specifically, I was reading these two resources: https://stackoverflow.com/questions/2282427/interesting-problem-currency-...
-2 votes
1 answer
169 views

Finding Cheapest n-Path [closed]

Given a weighted directed acyclic graph, how can I find the cheapest path from an Origin Vertex to a Destination Vertex which ...
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\}$. (...
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: ...
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 ...
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 ...
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[...
1 vote
0 answers
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 ...
-1 votes
1 answer
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 ...
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} + ...
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 ...
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 ...
1 vote
1 answer
139 views

K-fold Traveling salesman problem - A variant of TSP

Consider a weighted graph $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^...
1 vote
1 answer
232 views

Are there any heuristics that works solely on graphs?

I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work ...
2 votes
0 answers
631 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....
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 ...
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 ...
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, ...
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 ...
2 votes
2 answers
447 views

Why is label pruning possible with hub labeling?

Hub labeling (HL) computes superlabels using the vertices visited by the forward and reverse Contraction Hierarchies (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict ...
2 votes
0 answers
621 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 ...
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_{...
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 ...