A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [shortest-path]

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

63 questions
Filter by
Sorted by
Tagged with
11k views

### Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
6k views

### Finding the k-shortest path between two nodes

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-...
44k views

### Why does Dijkstra's algorithm fail on a negative weighted graphs? [duplicate]

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
4k views

### Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive. the algo depends on finding a new weight function (w') that ...
219 views
+50

### How hard is finding the shortest path in a graph matching a given regular language?

Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
2k views

### Minimum distance between start and end by going through must visit points in a maze

So, suppose i have a maze, which has a start point and an end point, marked with Orange and red respectively and my goal is to find the minimum distance between them. The blocked path is represented ...
42k views

### Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? ...
13k views

### Is there an algorithm to find all the shortest paths between two nodes?

Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes. What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all ...
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$ ...
3k views

### Example of graph with exponential many s-t minpaths and min cuts

I am trying to find a graph in which both s-t minpaths and min cuts are exponential. Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an ...
2k views

### Chess Knight minimum moves to destination on an infinite board

There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm. Here is ...
163 views

### Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
70k views

### Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
29k views

### Getting negative cycle using Bellman Ford

I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name ...
2k views

### Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
9k views

### Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...
1k views

### How many shortest distances change when adding an edge to a graph?

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
914 views

### Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random

Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ ...
2k views

### Finding shortest paths in undirected graphs with possibly negative edge weights

The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge ...
3k views

### Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a depth-...
485 views

### Given all pairs shortest paths matrix, find graph with minimum total sum of edges

I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some ...
13k views

### Finding paths with smallest maximum edge weight

I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge. In the above graph, the easiest path from 1 to 2 is: ...
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 ...
49 views

### Is the number of shortest paths between every two vertices at most 4*n^3?

In every weighted graph with $n$-vertices with negative weights, with $n > 10$, a weight can't appear $n$-times in graph, there are between every two vertices at most $4n^3$ shortest paths. I'm ...
334 views

### Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
797 views

### Modification of Dijkstra's algorithm

How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality? There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough ...
23k views

### Finding shortest and longest paths between two vertices in a DAG

Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are ...
17k views

### Shortest Path on an Undirected Graph?

So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
6k views

### Shortest path with exactly $k$ edges

From Skiena's book The Algorithm Design Manual, chapter 6, problem 22: Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ ...
2k views

Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes $\... 2answers 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 ... 3answers 1k views ### What is the meaning of 'breadth' in breadth first search? I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this: Breadth-... 1answer 277 views ### Shortest path when allowed to reverse an edge We're given an unweighted directed graph with vertices$V$and edges$E$. We're trying to find the shortest path from$s$to$t$but we're allowed to travel along up to one edge in the ... 2answers 401 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 ... 1answer 574 views ### Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly? I want to produce$k$shortest path ($k$would be less than 10) between all pairs in a graph. The graph is (actually a subway map): positively weighted undirected sparse with about 100 nodes My ... 1answer 857 views ### Linear time algorithm for finding$k$shortest paths from$s$to$t$Definition. Given a graph$G=(V,E)$and two vertices$s$and$t$, the$k$-shortest-paths problem is finding the$k$shortest simple paths between$s$and$t$in$G$. Note that the length of ... 1answer 2k views ### How to find the shortest path from some vertex in set$S$to set$S'$If i have a graph$G=(V,E)$, a subset of vertices$S \subset V$and a second set of vertices$S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That ... 2answers 2k views ### Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop The Floyd-Warshall algorithm is defined as follows: ... 1answer 619 views ### Finding the lowest-weight negative cycle in a weighted digraph Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible? I know that I can detect ... 1answer 373 views ### Shortest path problem where edge weight depends on path taken I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between ... 1answer 4k views ### All paths of less than a given length in a directed graph between couple of nodes Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, ... 1answer 4k views ### Running Floyd-Warshall algorithm on graph with negative cost cycle I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, ... 1answer 2k views ### What is the maximum number of shortest paths between any pair of vertices in a chordal graph? A graph$G$is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree$T$of$G$is a ... 1answer 535 views ### An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries Is there an incremental directed graph data structure that has the following properties: Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-... 2answers 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, ... 1answer 2k views ### Shortest path from that passes through a set of edges once Given a graph with weighted edges. How to find the shortest path from vertex$A$to vertex$B$that passes through a set of edges$X$at most once?$X$can be big. Slow solution: Finding shortest ... 1answer 723 views ### Shortest directed path connecting given subset of vertices Given weighted directed graph$G = (V,E,w)$, where$w : E \to \mathbb R^+$source vertex$v \in V$vertex subset$U \subset V$how to find a shortest directed path from$v$containing all vertices ... 1answer 420 views ### When is the output of shortest path$\subset$MST? I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like: The shortest path$B \...
Suppose for each positive integer $N$, we have a graph $G_N$ with $N$ vertices labelled $1$ to $N$ (so $\log N$ bits are required to specify a vertex). Suppose we have a PSPACE algorithm to determine ...