Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
0 votes
2 answers
53 views

Calculate shortest cycle that contains node $s$

Let $ G(V,E,w)$ be a graph with no negative weights. Describe an algorithm that returns the shortest cycle containing a node $ v $. I came across this algorithm https://courses.engr.illinois.edu/cs374/...
user avatar
1 vote
1 answer
40 views

Algorithm to compute cheapest path between two pixels in an image

I need to compute the cheapest path between two pixels in an image. The travel cost is specified by the user, and may depend on the distance between the pixels (including pixel values, which is ...
user avatar
0 votes
1 answer
42 views

Any-goal bidirectional A* pathfinding reference

I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that ...
user avatar
  • 121
1 vote
1 answer
28 views

Correctness of bft resulting in shortest path

I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path: source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf The ...
user avatar
0 votes
2 answers
55 views

Find a simple path from S to T in a directed graph so that the product of its weights is maximum

I'm looking for an algorithm that finds a simple path from S to T in a directed graph (which might have cycles) so that the product of edge weights in the path is maximum. All the edge weights of the ...
user avatar
  • 23
2 votes
0 answers
39 views

Is there an efficient algorithm for calculating shortest path for multiple (source,target) pairs in a graph?

I wonder if there is an algorithm which takes multiple (source,target) pairs and a max_depth parameter and returns all or some of the paths found with those pairs? Thinking of Dijkstra's algorithm, it ...
user avatar
2 votes
1 answer
537 views

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

The problem concerns finding shortest paths in graph from a single source to a single destination. So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
user avatar
0 votes
1 answer
102 views

Is there an edge whose removal will extend the shortest path? - graph problem

Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal ...
user avatar
  • 71
1 vote
1 answer
47 views

Subpath optimality lemma in weighted undirected graphs

In an introductory course on Dijkstra's algorithm, I enunciated the following lemma : Let x →* z be a shortest path in a weighted graph and let y be any vertex along that path. It follows that x →* y ...
user avatar
  • 233
0 votes
1 answer
113 views

why use bellman-ford instead of Dijstra in RIP routing?

The RIP routing protocol was published in 1988 and uses Bellman-Ford algorithm to calculate shortest path. Also more recent version of RIP (RIPv2 and RIPng) use the same algorithm. The Djikstra ...
user avatar
  • 103
0 votes
0 answers
16 views

Are all sub paths of an optimal A* path optimal?

This question may be applicable to more than just A*. Let's say you have a grid of tiles, with some obstacles between tiles t0 and ...
user avatar
6 votes
1 answer
369 views

What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?

I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from Introduction to Algorithms by Cormen et al. The $w$ parameter is the weight function such ...
user avatar
1 vote
0 answers
33 views

compute shortest distance to a different sink

Given a directed graph G=(V, E) and a sink vertex t. Edge costs may be negative, zero, or positive. consider d(v) contains the length of the shortest path from v to t Given a new sink t2 in the graph, ...
user avatar
0 votes
0 answers
25 views

Updating Shortest Path Weight from One Destination to Another

Let $G=(V,E)$ be a directed graph with possibly negative edge weights. Given a destination $t$. Suppose that we have already known $d_v$, the shortest path weight from $v$ to $t$. If I'd like to ...
user avatar
  • 121
1 vote
0 answers
30 views

Shortest path with vertex capacity

I have an undirected graph where each edge $e=\{u,v\}$ has a positive weight $w_{uv}$ and each vertex $v$ has a positive capacity $c_v$. There are two special vertices: a source vertex $s$ and a ...
user avatar
  • 1,016
1 vote
0 answers
113 views

Min weighted path in a graph, but you could die

The min-path problem is mostly motivated by a graph with cities as vertices and roads between them as edges. Each edge has a weight which could be the length of the road or the time it takes to cross ...
user avatar
0 votes
1 answer
69 views

extending bellman ford to find shortest weight paths with no repeating vertices

Is it possible to extend the Bellman Ford algorithm to output all shortest simple paths without repeating vertices? The issue is that the Bellman Ford algorithm doesn't make any checks for whether the ...
user avatar
2 votes
1 answer
184 views

The distinct-vertex $\alpha$-edge variant of the all-pairs shortest paths problem

The following problem is a variant of the all pairs shortest path problem: Given a weighted, directed graph $G=(V,E), |V| = n,|E| = m,$ and an integer $\alpha\ge 1$, how can I find an efficient ...
user avatar
3 votes
1 answer
86 views

Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting ...
user avatar
0 votes
1 answer
26 views

Bellman Ford may not update distance correctly by termination?

Consider the example shown in the above figure. Let's consider two orders (1) S, A, B and (2) S, B, A for traversing the graph and updating the distance d (numbers in circle are distance d): 1- start ...
user avatar
1 vote
1 answer
125 views

How to find the lightest path that has at least one vertex of each color?

I've faced this question in my homework. In a graph $G=(V,\ E)$ where every $v\in V$ has a color, a colored path is a path such that it has at least one vertex of each color. We're given a directed ...
user avatar
1 vote
0 answers
26 views

Node domination in constrained path search

It's possible to modify a graph search algorithm such as Dijkstra's or A* to allow for non-additive objectives or constraints. Is there a standard treatment for these algorithms to reduce unnecessary ...
user avatar
  • 222
1 vote
1 answer
48 views

Finding 2 paths between 2 source-target pairs

Given an undirected graph $G=(V,E)$ and 2 sources $s_1,s_2$ and 2 targets $t_1,t_2$, I am looking to find paths $P_1$ and $P_2$, where $P_i$ is a path from $s_i$ to $t_i$ and $P_1$ and $P_2$ are edge-...
user avatar
2 votes
1 answer
50 views

Flow with edge-weight restrictions

I am given a graph $G=(V,E)$ undirected and two vertices, the source vertex $s$ and the target vertex $t$. Additionally, each edge comes with a capacity $c(e)$ (non-negative) and a set of weight ...
user avatar
4 votes
0 answers
51 views

Algorithm to find equivalent classes of homotopic pathes on a grid with obstacles

Given a $n \times n$ grid with some walls and two cells $a$ and $b$, I want to compute the non-homotopics paths from $a$ to $b$ on this grid. A path is a sequence of adjacent cells (diagonal does not ...
user avatar
  • 141
2 votes
1 answer
84 views

D* Lite - can edge costs be asymmetric?

I'm trying to modify the original D* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between ...
user avatar
  • 145
1 vote
1 answer
55 views

If the distance to a vertex is updated in the n-th relaxation of Bellman Ford, is that vertex on a negative-weight cycle?

Recently I asked a question Here about following topics: after finishing bellman ford algorithm, if BF continue to update distances and distance value related to one vertex v being updated,then v is ...
user avatar
1 vote
1 answer
103 views

bellman ford and one surprizing fact

I ran into a very surprising local contest problem. after finishing bellman ford algorithm, if we continue to updating distance and distance of one vertex v being updated, then v is on negative cycle....
user avatar
0 votes
1 answer
62 views

How can i do this type of swap(4-opt) between 4 edges of a graph?

The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
user avatar
2 votes
1 answer
68 views

Set of Pareto-optimal paths, in a graph where edges have both length and cost

Suppose I have a graph $G=(V,E)$, where each edge $e$ has both a non-negative length $\ell(e)$ and a non-negative cost $c(e)$. Given a start node $s$ and a destination node $t$, I want to find a set ...
user avatar
  • 141k
2 votes
1 answer
40 views

Retrieving the cheapest path of a graph with time-dependent edge weights

There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient ...
user avatar
  • 21
1 vote
1 answer
67 views

Euler Tour in Christofides Algorithm

The penultimate step of the Christofides algorithm in solving the TSP asks us to find an Eulerian tour of the subgraph formed by uniting the MST of the original graph and MPM of a subgraph. I ...
user avatar
7 votes
0 answers
295 views

Shortest path in directed graphs with no more than $\log \log n $ negative edges

Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$, I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does ...
user avatar
  • 55
3 votes
1 answer
70 views

Shortest possible path between closest pair of specific nodes in a maze

Need to find the shortest distance between the closest pair of 'r' and 'b' nodes. You can traverse along '.' elements, but not 'o' elements. How can we do this in $O(MN)$ time? (M rows, N cols). $O(...
user avatar
  • 55
10 votes
2 answers
2k views

Find shortest path between two vertices that uses at most one negative edge

Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$: Describe an ...
user avatar
  • 228
1 vote
1 answer
78 views

Shortest walk from $u$ to $v$ through $w$

We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W_1(e) &...
user avatar
  • 21
0 votes
1 answer
78 views

Algorithm to find shortest distance from source to all other vertices of graph in O(m)?

My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
user avatar
  • 55
1 vote
0 answers
81 views

Shortest path as a linear program

I just encountered this formulation of the shortest $s$-$t$ path problem as a linear program in a homework. I don't understand exactly the meaning of the variables and restrictions. Here, $G = (V, E)$ ...
user avatar
4 votes
1 answer
35 views

Is there a more efficient way to obtain the optimal input sequence in this finite-state system

Context: Consider $M$ finite state systems with evolution given by: $$ x^i_{k+1} = f(x_k^i,u_k) $$ where $x_k^i\in\{1,\dots,X\}$ is the state of system $i\in\{1,\dots,M\}$, $k\geq 0$, and $u_k\in\{1,\...
user avatar
0 votes
0 answers
48 views

Finding the shortest path with this algorithm

This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
user avatar
  • 115
3 votes
1 answer
61 views

Algorithm to find the shortest path and its length for moving between many geometries

I have a set of 2D geometric figures in Cartesian space, as shown in the image. Each geometric figure has a start point and an end point (among other characteristics). For closed geometries, such as a ...
user avatar
  • 33
1 vote
1 answer
82 views

Why can't we use BFS with modifications to find shortest paths in weighted graphs

I came across this post about how we can get to all shortest paths from source (u) to destination (v) . If the algorithm is working in O(E + V), why can't we use it (after slight modifications) for ...
user avatar
3 votes
1 answer
273 views

Finding the most profitable path

I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this. To put it simply, the problem is the following: We want to go from ...
user avatar
0 votes
0 answers
220 views

Number of shortest paths between two nodes in undirected unweighted graph

I'm trying to devise a $O(|V| + |E|)$ algorithm to calculate number of shortest paths between $s$ and $f$ on a undirected, unweighted graph. Can someone please check my pseudo-code? Also, isn't $O(|V| ...
user avatar
  • 113
1 vote
1 answer
93 views

Algorithm to find the path with minimum bending points on a square grid board

Let's suppose we have a square grid board like the one shown in the picture below: I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
user avatar
3 votes
3 answers
2k views

Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?

Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V ...
user avatar
  • 33
2 votes
0 answers
35 views

Shortest path in a tree

Is it correct to talk about shortest path in a tree, isn't a tree has only single path between any two nodes ?
user avatar
0 votes
0 answers
28 views

Algorithm to efficiently plan a path to build a pixel structure

I have a problem that I have an unsatisfactory answer to and I would be interested in knowing if there is a better solution I am missing. The problem is as follows: Compute a series of ...
user avatar
0 votes
0 answers
52 views

A relaxation-free variant of Dijkstra's shortest path algorithm

I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
user avatar
  • 1,071
0 votes
0 answers
39 views

Finding the shortest distance between two nodes given multiple graphs

Assume that we have a set of nodes and multiple graphs with different edge values for the same set of nodes. As an example, there are 4 nodes A, ...
user avatar

1
2 3 4 5
13