12 votes
Accepted

Number of simple paths between two vertices in a DAG

Every simple path is uniquely determined by the subset of vertices that it passes through: if you topologically order the DAG (arbitrarily) then a path through any subset of vertices must go through ...
8 votes
Accepted

Shortest distance problem with length as functions of time

This is known as the "time-dependent shortest path" problem. Indeed research has been done for this problem; see for example the classical paper by Orda and Rom, and this recent SODA paper which ...
7 votes
Accepted

Finding the two shortest paths while minimizing the number of nearby/common edges

If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$...
  • 3,430
5 votes
Accepted

Axioms for Shortest Paths

I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in this paper that I might as well share. I hope the combination of thread ...
  • 2,313
5 votes
Accepted

Are there any heuristics that works solely on graphs?

There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known ...
4 votes

Constant Width Max Sum Product Multi-objective Shortest path problem

For K=2, PARTITION reduces to this problem, so it is NP-hard. Take an instance of PARTITION: a list of nonnegative integers $x_1,\dots ,x_n$, and you ask if there is a subset $I\subseteq [1,n]$ such ...
  • 7,747
4 votes

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

Indeed: Eppstein has shown that the TSP can be solved in time $O(1.26^n)$ if all vertices are of degree at most 3. David Eppstein: The Traveling Salesman Problem for Cubic Graphs. J. Graph ...
  • 5,722
4 votes

Finding k shortest Paths with Eppstein's Algorithm

Pseudocode for Eppstein's algorithm (and the authors' lazy version of it) are given in: V.M. Jiménez, A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop ...
  • 41
3 votes
Accepted

Finding shortest path while maximizing the number of overlapping edges

There is a polynomial-time algorithm for this problem in the case where $C \le 2$. There is also a polynomial-time algorithm when $C > 2$, assuming paths are not required to be simple. If you ...
  • 10.5k
3 votes
Accepted

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

Yen's original paper 1, from 1971, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1). Lawler's original paper 2, from 1972, improves the time complexity upper bound to $O(Kn^3)$. ...
  • 4,361
3 votes
Accepted

Minimum Union-Sum Cost Path

EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$...
  • 8,281
3 votes

Bellman-Ford with Non-edge-decomposable Path Weights

No, Bellman-Ford won't work because the problem you described is NP-hard. This is pretty easy to prove. I've been able to come up with several reductions using the same strategy. The general idea is ...
3 votes
Accepted

Shortest path on a hypergraph with no leftovers

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete. Lemma 1. Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph ...
  • 8,281
3 votes
Accepted

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

The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a ...
  • 1,432
3 votes
Accepted

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

Considering your response in the comments where you do not necessarily need a provably-better runtime: Have a look at the three methods described in this tutorial: https://www.hackerearth.com/...
  • 1,237
3 votes

Shortest distance problem with length as functions of time

Are you aware of the "shortest nondecreasing paths" problem? It was defined to model situations such as these. Although it's a bit less expressive compared to your formulation, there are fast algs for ...
3 votes

Cooperative Pathfinding to minimize global costs

This may be related to network formation games - games in which players try to find a path in a network, and collaborating along a path reduces the cost for both players (i.e. the cost is shared) This ...
  • 5,281
3 votes

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

The discussion in this paper, Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP ...
  • 2,313
2 votes

Ref question: K-nearest neighbours in a graph

In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe ...
2 votes

Highway dimension

I think highway dimension is a formalization of a physical property for roadmaps. Assume that you have a large country. You want to get from one small city to another one. If the cities are far ...
2 votes

Dynamic programming and shortest path problem

Here's a less formal answer that I hope nonetheless addresses the spirit of the question. Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-...
  • 8,281
2 votes
Accepted

Max Sum Product Multi-objective Shortest path problem

It seems NP-complete even with weights in $\{0,1\}$. I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses. More precisely, an ...
  • 7,747
2 votes

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

I think the first proof was given in Der-Tsai's 1978 thesis on pages 111-113. With the above result it is immediate to realize that the shortest path problem with line segments as obstacles can ...
2 votes
Accepted

Proof of SPFA's worst-case complexity?

Here's the algorithm (from the wikipedia page) then a proof of the time bound: ...
  • 8,281
1 vote
Accepted

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

In general, your problem is NP-hard, naturally (if you have arbitrarily many agents and an arbitrary arena, of course). Combining paths will naturally cause collisions (otherwise we wouldn't need ...
  • 5,281
1 vote

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

Yes there is no reason to add the extra vertex $v_0$ since the graph is fully connected and every vertex is reachable from every other vertex (the table specified in the problem seems to be a complete ...
1 vote

Finding Cheapest n-Path

I am assuming you are given a weighted directed acyclic graph with source $s$ and destination $t$ and you want to find the shortest path from $s$ to $t$ with length exactly $n$ , this can be done ...
1 vote
Accepted

Maximum difference between two shortest paths

There exists an optimal solution $p,q,c$ such that $c_e = l_e$ for all edges $e$ in the path $q$ and $c_e = u_e$ otherwise. For the optimal solution from point 1 exists a vertex $x$ at which the paths ...
1 vote

Multiple source shortest path with one reversal

You can start by converting your graph $G = (V, E)$ into a new graph $G'$ as follows: The vertices of $G'$ should be $V \times \{0,1\}$. For every vertex $v \in V$, include the edge from $(v, 0)$ to ...
1 vote

K-fold Traveling salesman problem - A variant of TSP

There was a paper on the arxive last month, dealing with this generalization of the TSP: The multi-stripe travelling salesman problem Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger (...
  • 5,722

Only top scored, non community-wiki answers of a minimum length are eligible