# Questions tagged [shortest-path]

The tag has no usage guidance.

75 questions
Filter by
Sorted by
Tagged with
115 views

### Three questions about the LPA* algorithm

I have a few questions about the LPA* algorithm, I think I know the answers to most of these questions, but I just wanted to be sure. Here is the pseudocode for reference: and here is the link to the ...
• 9
46 views

### Breaking ties in A* to produce same path as D*lite

What tie breaking criteria do I need to implement in A* to mimic exactly the same behaviour as D* lite. Ofcourse both algorithms use the same heuristic and cost functions. So basically if I run A* ...
• 9
100 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, ...
• 33
1 vote
61 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 ...
• 119
50 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 ...
46 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....
• 101
354 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 ...
• 201
223 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 ...
• 1,448
137 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 ...
• 2,183
354 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 ...
• 451
1 vote
2k 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$...
109 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 ...
• 175
160 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-...
• 115
155 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 ...
• 97
304 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: ...
• 43
543 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 ...
• 33
499 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 ...
• 175
557 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 ...
9k views

182 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} + ...
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 ...
• 363
386 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 ...
1 vote
207 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 ...
581 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....
• 161
87 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 ...
233 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, ...
86 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 ...
• 161
554 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 ...
194 views

• 7,350
431 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 ...
• 159
151 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 ...
• 221
1 vote
2k views

### Run Dijkstra's algorithm twice to detect negative-weight cycles?

Dijkstra's algo (for finding single-source shortest path) assumes that once a vertex has been chosen for expansion (aka exploration), its shortest path has been found. This can only be true if there ...
259 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 ...
267 views

• 1,102
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$, ...
• 509
792 views

### Self-avoiding walk in Graph [closed]

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...
• 169
214 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 ...
• 169
I have a directed graph which has cycles. Each edge has a positive weight. Now given two vertices $u$ and $v$, I want to find the longest simple path from $u$ to $v$. Simple means the path has no ...