Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
953 views

Finding all paths with lengths in a fixed interval in sparse graphs

What is the most efficient way to find all paths of length M to N in a large sparse graph? Some general information: Graph has 30,000 to 50,000 nodes Average number of edges per node ~ 10 M=4, N=7 ...
2
votes
0answers
119 views

Update SSSPP solution on complete digraph on weight changes

I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative. On various occasions '...
42
votes
3answers
40k 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 ...
5
votes
1answer
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-...
3
votes
0answers
918 views

Any algorithm for finding Euclidean shortest path with specific constraints in 2D?

I have the following problem: In a 2D space with polygonal obstacles, find the shortest path between two given point. Without additional constraints, we can reduce it to a graph problem by ...
0
votes
1answer
3k views

How to optimize Dijkstra's algorithm for a grid graph?

I'm trying to apply Dijkstra's algorithm to the Problem 83 on projecteuler.net. The problem reads: In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by ...
2
votes
1answer
2k views

Non intersecting paths in a graph

I'm trying to come up with a good algorithm for the following decision problem: Let $G=(V,A)$ be a directed graph and let $s,t \in V$. Are there at-least 2 non-intersecting paths from $s$ to $t$? By ...
3
votes
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 ...
1
vote
1answer
1k views

Find least probable path in graph

I am working on a special case of the longest path problem. For a cyclic directed graph $G=(V, E)$, where the edge-weights are probability values (i.e., $P(\_) = w(s, q)$ with $s,q \in V$), my aim is ...
9
votes
1answer
5k 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}$-...
45
votes
7answers
67k 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 ...
5
votes
2answers
676 views

Path finding under constraints

Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the ...
2
votes
1answer
270 views

Can Floyd-Warshall be used to solve an APSP problem without copying the matrix?

According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration? What I mean is, according to CLRS: $...
4
votes
2answers
119 views

Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random, The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of ...
6
votes
1answer
420 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
14
votes
2answers
878 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$ ...
14
votes
2answers
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 ...
4
votes
1answer
5k views

A* to find the longest path in a directed cyclic graph

I have written an A* algorithm to find the shortest path through a directed cyclic graph. I am trying to modify it to find the longest path through the same graph. My attempt was to write it so that ...
7
votes
2answers
12k views

Shortest path that passes through specific node(s)

I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an ...
6
votes
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, ...
4
votes
1answer
512 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-...
3
votes
2answers
2k views

Shortest Minimax Path via Floyd-Warshall

I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.) Floyd-...
6
votes
1answer
335 views

Approximability of the edge-disjoint shortest paths problem

In the edge-disjoint paths problem (EDP), we are given a (possibly directed) graph $G=(V,E)$, and a set of distinct source-sink pairs $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$, and we want to maximize ...
2
votes
1answer
225 views

Finding path with minimum weight

There is a river which can be considered as an infinitely long straight line with width W. There are A piles on the river, and B types of wooden disks are available. The location of the $i$-th pile ...
4
votes
1answer
1k views

Can the shortest simple cycle between two given nodes be found in polynomial time?

Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, ...
3
votes
0answers
3k views

Route planning in public transport application [closed]

This is a cross-post of this StackOverflow question, (I'm not aware of linking questions between StackExchange sites). You can ignore the part about programming. I'm making a journey planner (or a ...
2
votes
0answers
147 views

Multicommodity shortest path problem on a directed acyclic graph

I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
1
vote
1answer
81 views

For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?

Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of ...
-2
votes
1answer
385 views

Find the weight of the lightest path from u to v

Find the weight of the lightest path from u to v the goes through node a or/and b. Do you have a suggestion on how it can be done?
6
votes
2answers
2k views

Finding all vertices on negative cycles

Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a ...
2
votes
2answers
1k views

Shortest path with odd weight

Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd. We are looking for an algorithm for finding the weight of the shortest odd ...
4
votes
1answer
9k views

Finding the path of a negative weight cycle using Bellman-Ford

I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, ...
2
votes
1answer
251 views

Shortest paths candidate

Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. ...
4
votes
1answer
5k 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$ ...
1
vote
1answer
513 views

Bellman-Ford parent pointer (?) negative cycle

First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof ...
5
votes
1answer
625 views

Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves

This problem is about finding a route on a square grid. The starting point is $(1,1)$ and the target point $(n,m)$. I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$. ...
6
votes
4answers
3k views

Solving system of linear inequalities

I am trying to solve a system of inequalities in the following form: $\ x_i - x_j \leq w $ I know these inequalities can be solved using Bellman-Ford algorithm. ...
13
votes
2answers
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 ...
-1
votes
1answer
255 views

WP pseudocode for Dijkstra does not work

I mean Dijkstra's algorithm for the shortest path. In all descriptions that I saw (including wikipedia), on every step, it always selects the nearest neighbor based on examining their weights. ...
8
votes
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, ...
4
votes
3answers
606 views

Find a vertex that is equidistant to a set of vertices?

I need help with the following problem: Input: An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$. Question: Find a vertex $v$ of $V$ such that the distance ...
3
votes
1answer
7k views

Destination-based vs source-based routing

I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-...
6
votes
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 ...
-1
votes
3answers
861 views

Dijkstra algorithm: equal number of shortest paths

If I had a Dijkstra graph with the number shortest paths from Node A to O being 1, would it be correct to say: the equal number of shortest paths from A to O is 1 and not 0, because that node is ...
21
votes
2answers
27k views

Is Dijkstra's algorithm just BFS with a priority queue?

According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
5
votes
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: ...
1
vote
1answer
127 views

Path on an edge-colored DAG using exactly $k$ colors

I have the following problem: Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$, does there exist a path from $s$ to $t$ using exactly $k$ ...
4
votes
1answer
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$ ...
-1
votes
3answers
305 views

BFS in K shortest paths

Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes? If so where can it be useful?
5
votes
2answers
523 views

Why not relax only edges in Q in Dijkstra's algorithm?

Can someone tell me why almost in every book/website/paper authors use the following: foreach vertex v in Adjacent(u) relax(u,v) when relaxing the edges, ...