We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [shortest-path]

The tag has no usage guidance.

64 questions
Filter by
Sorted by
Tagged with
908 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. ...
454 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 ...
9k 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 ...
501 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 ...
329 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 ...
110 views

### What are the differences between Theta* and Field D*?

Both Theta* and Field D* are variations on the A* algorithm, but are adapted for any-angle pathfinding rather than pathfinding constrained to a grid. The primary difference between these two ...
5k 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 ...
189 views

### Dynamic k-shortest paths in a weighted transducer

I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly. In this scenario ...
371 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 ...
2k views

### Implementing D* Lite for Path-Planning - How detect Edge Cost Change?

I currently try implementing the D* Lite Algorithm for path-planning (see also here) to get a grasp on it. I found two implementations on the web, both for C/C++, but somehow couldn't entirely follow ...
624 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 ...
1k 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, ...