Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [shortest-path]

Questions about the algorithmic problems of finding shortest paths between nodes in a graph.

471 questions
Filter by
Sorted by
Tagged with
6k views

### Shortest path in weighted(positive or negative) undirected graph

I have to find an algorithm that finds the SSSP (single-source shortest path - shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different ...
5k views

### What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?

Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$. What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ ...
247 views

### Modified Djikstra's algorithm

So, I'm trying to conceptualize something: Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats: movements on ...
281 views

### Looking for an algorithm to find a shortest path in a special graph

I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special ...
2k views

### Proving that the shortest path problem between two vertices $s$ and $t$ in a graph is NP-complete

How to show that the Shortest path problem between two vertices $s$ and $t$ (finding a minimum weighted path between $s$ and $t$) in a graph is NP-complete? I received the following prof in ...
345 views

### Complexity of shortest paths if paths have to use edges from different partitions

We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully ...
317 views

### Can a shortest-path tree be a also maximum spanning tree?

If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example! I ...
360 views

### Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...
129 views

### Given an oriented graph, return true if paths have a specified length

I'm having trouble solving this exercise about graphs, I hope you can help me: Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an ...
3k views

### What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
202 views

### How to reduce the cost of search based on previous BFS?

I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles. My goal is to output a map, based on given location on the ...
313 views

### How to perform local search on simple paths?

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph. The question is: given a current ...
35 views

### Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
84 views

### Can the running time be reduced to something lower than $O(d^4)$?

Imagine I have a weighted complete directed graph $G$ with $d$ vertices(so $d(d-1)$ edges) and I want to do the following: Set $D$ to be a DAG with the same set of vertices but without any edges sort ...
677 views

### A good heuristic for 2D Rubik's cube

I am looking for a good heuristic function for solving a 2D $n\times n$ Rubik's cube using A* search. There is a game already in the play store. The rules of the game: Swiping LEFT means the ...
143 views

### MST that contains a shortest $s,t$-path

Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$...
124 views

### Successive Shortest Paths vs Ford–Fulkerson

Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page ...
3k views

### Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
652 views

### What is the complexity of Hoffman and Pavley's Nth best path algorithm?

I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
991 views

### The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm

In the Floyd-Warshall algorithm we have: Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to $j$ for which all intermediate vertices are in the set $\{1, 2, \cdots, k\}$ then \...
1k views

### Can I run Dijkstra's algorithm using priority queue?

I think I can run Dijkstra's algorithm using any data structure. I do not see any implementation details of Dijkstra's algorithm. Is a priority queue a possible data structure? Will running Dijkstra'...
155 views

### Which graph algorithm should I use?

I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time ...
811 views

770 views

### Algorithm: Shortest path (walk) with keys and doors

I'm trying to solve the following algorithm question: A maze is given by a graph (with let's say $v$ vertices and $e$ edges), where $k$ vertices are different keys and, $k$ vertices are the ...
1k views

### Does the A* algorithm visit every node?

I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, ...
1k views

### Dijkstra's algorithm to compute shortest paths using k edges?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...
8k views

### Dijkstra's algorithm for edge weights in range 0, …, W

Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range 0, ..., W, where W is a relatively small number. How can I modify that algorithm so that it takes ...
517 views

### Multiple Source Shortest Paths in a weighted graph

In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at ...
156 views

### Shortest Path in a Graph with Interacting Edge Weights

Suppose we have a graph $G = (V,E)$. Every edge $e \in E$ has a unary cost $f(e) > 0$. Also, for every two edges $e_1,e_2 \in E$ we have a binary reward function $g(e_1,e_2) \geq 0$. Given two ...
At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...