Questions tagged [shortest-path]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
1 answer
191 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
1 vote
1 answer
410 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 ...
E. Turok's user avatar
6 votes
1 answer
303 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
3 votes
1 answer
226 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
1 vote
0 answers
69 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 ...
user49404's user avatar
  • 119
-1 votes
1 answer
81 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....
Sayan Dey's user avatar
  • 101
11 votes
1 answer
519 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 ...
user514014's user avatar
4 votes
1 answer
323 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,498
8 votes
0 answers
162 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,393
1 vote
1 answer
427 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 ...
Mengfan Ma's user avatar
1 vote
1 answer
4k 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$...
Iago Carvalho's user avatar
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 ...
mnmp's user avatar
  • 175
-1 votes
1 answer
170 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-...
Hunle's user avatar
  • 115
-2 votes
1 answer
167 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 ...
Reubend's user avatar
  • 97
4 votes
1 answer
384 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
3 votes
1 answer
691 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
4 votes
1 answer
533 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
2 votes
1 answer
587 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
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
1 vote
0 answers
118 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 ...
Phyr's user avatar
  • 11
-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 ...
Hamster Hooey's user avatar
1 vote
1 answer
137 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)^...
Vivek Bagaria's user avatar
3 votes
1 answer
194 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
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
  • 363
3 votes
1 answer
497 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
1 vote
1 answer
228 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 ...
Bora M. Alper's user avatar
2 votes
0 answers
621 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....
Stanley F.'s user avatar
2 votes
1 answer
94 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
5 votes
1 answer
256 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
90 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
2 votes
0 answers
613 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 ...
user avatar
3 votes
1 answer
210 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
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 ...
Satabdi Aditya's user avatar
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
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
  • 11.7k
7 votes
2 answers
353 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
2 votes
1 answer
777 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
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
0 votes
0 answers
248 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 ...
Phylliida's user avatar
  • 1,132
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
  • 8,916
2 votes
2 answers
441 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 ...
Chris's user avatar
  • 159
0 votes
0 answers
162 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 ...
linello's user avatar
  • 221
0 votes
1 answer
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 ...
Alexandre Holden Daly's user avatar
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
280 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,438
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
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
-5 votes
1 answer
813 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 ...
Ilya Gazman'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
-2 votes
1 answer
1k views

What's wrong with my linear programming formulation of longest path? [closed]

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 ...
Janathan's user avatar