Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
6
votes
1answer
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: ...
6
votes
1answer
255 views

Building vertex-edge visibility graph among polygonal obstacles on 2d plane

I want to implement algorithm for computing vertex-edge visibility graph among polygonal obstacles, but I can't find any description or scientific paper describing such algorithm. Currently I ...
6
votes
1answer
341 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 ...
6
votes
1answer
8k views

Formalization of the shortest path algorithm to a linear program

I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem: For a graph $G=(E,V)$, we defined $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid h(...
6
votes
0answers
1k views

Suurballe's Algorithm: Proof of Correctness

I was reading about Suurballe's algorithm on Wikipedia, for the shortest edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
6
votes
0answers
329 views

Are there Some Pairs Shortest Paths Algorithms?

I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes. The properties ...
6
votes
0answers
1k views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
6
votes
1answer
432 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 ...
5
votes
2answers
542 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, ...
5
votes
2answers
1k views

Shortest path between two points with n hops

Is there an efficient algorithm which computes the (possibly approximately) shortest $n$-edge path between two points $A$ and $B$ in a weighted complete graph? Dijkstra won't work because it will just ...
5
votes
1answer
900 views

Dijkstra with max instead of sum

Is it true that if we replace in the Dijkstra algorithm + with max, then the resulting algorithm correctly solves the problem of ...
5
votes
2answers
1k 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 ...
5
votes
1answer
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 ...
5
votes
2answers
3k views

Algorithms: Difference Constraints

I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem: Consider the following set of difference constraints: ...
5
votes
2answers
1k views

Adding a node between two others, minimizing its maximum distance to any other node

We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a ...
5
votes
1answer
4k 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-...
5
votes
1answer
626 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)$. ...
5
votes
1answer
282 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 ...
5
votes
2answers
1k views

Data structure for A*'s “open” set

I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet ...
5
votes
1answer
1k views

Is the “Bidirectional Dijkstra” algorithm optimal?

In some sites they say the bidirectional Dijkstra's algorithm is optimal, e.g., this, and this. Also there is some software that uses this algorithm (for example this DBMS). But some posts express ...
5
votes
2answers
847 views

Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

This is from CLRS problem 24.3-5: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$ . Give ...
5
votes
1answer
315 views

Mean and median distance in unweighted graph

I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds. The graph is an unweighted directed strongly connected graph. I ...
5
votes
2answers
2k views

Shortest path between 2 vertices using at most K edges using Bellman-Ford

I'm a bit confused about stopping at Kth iteration on the Bellman-Ford algorithm to find the shortest path of at most length k from s to t. Let me show you a graph and explain you what I understand: ...
5
votes
1answer
635 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 ...
5
votes
1answer
1k views

Bellman-Ford Termination when there is no change on vertex weights?

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the ...
5
votes
1answer
7k views

Finding the Shortest path in undirected weighted graph

Is there an algorithm for finding the shortest path in an undirected weighted graph?
5
votes
2answers
2k views

Recalculating shortest path after changing the weights

I have a weighted, directed graph. I do the following. Given nodes $s$ and $t$ I compute shortest path. Then, I decrease weights of some edges and want to see if there is now another shortest path. Of ...
5
votes
1answer
152 views

K shortest paths - any relation between K and % of graph nodes in discovered paths?

Let's say I have a graph with $N$ nodes, $A$ arcs and an average branching factor $b$. I want to find the $K$ shortest paths between two nodes. Is there some relation (even approximate is fine) that ...
5
votes
0answers
84 views

Find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance. ...
5
votes
2answers
702 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 ...
5
votes
1answer
554 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
4
votes
3answers
6k views

Dijkstra's algorithm for undirected graphs with negative edges

INPUT: "an undirected, weighted graph (negative weights allowed)" Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work? As far as i ...
4
votes
1answer
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$ ...
4
votes
2answers
569 views

Dijkstra with bitwise OR of edge costs

Given a graph $G$ where loops and multiple edges are allowed. A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost $$ cost = e_1 | e_2 |...|e_k$$ where $|$ is the bitwise OR. Assume for all ...
4
votes
3answers
670 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 ...
4
votes
2answers
3k views

Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding ...
4
votes
1answer
1k views

Finding all edges on any shortest path between two nodes

Given a directed weighted graph with non-negative weights, how can I find all edges that are a part of any of the shortest paths from vertex X to Y? In the example below the yellow edges are the ...
4
votes
2answers
210 views

Graph Algorithm (Modification on Dijkstra?) : Tech Interview

Problem: Suppose we had a directed graph $G(V,E)$ with strictly positive edge weights, a nonempty set $A$ (special vertices) such that $A \subseteq V$, a positive integer $C$, and a starting vertex $S ...
4
votes
2answers
14k 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 ...
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 ...
4
votes
2answers
2k views

Minimum-weight shortest-path tree

How can we compute the shortest-path tree of minimum total weight for a given connected graph? I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one ...
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 ...
4
votes
1answer
2k 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, ...
4
votes
1answer
526 views

Algorithm to find the shortest walk with k leaf nodes on a tree

Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root? Passing through a node/...
4
votes
1answer
6k views

Comparison between IDA* and Recursive best first search

How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity? Both algorithms are intended to be memory-efficient heuristic ...
4
votes
1answer
546 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-...
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, ...
4
votes
1answer
51 views

Optimal root in shortest path tree (SPT)

I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs. ...
4
votes
1answer
126 views

Modifies Dijkstra’s Algorithm to find the maximum cost path

In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?
4
votes
1answer
103 views

Path between two vertices in directed graph without cyclic vertices

I have been searching online for some time but I have not found an answer. Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic ...

1 2 3 4 5 10