Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
595
questions
4
votes
0answers
31 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 ...
2
votes
1answer
70 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 ...
0
votes
1answer
29 views
strange and different conclusions about Bellman Ford
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 ...
1
vote
1answer
77 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....
0
votes
1answer
41 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). ...
2
votes
1answer
28 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 ...
2
votes
1answer
26 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 ...
1
vote
1answer
49 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 ...
7
votes
0answers
212 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 ...
3
votes
1answer
58 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(...
10
votes
2answers
1k 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 ...
1
vote
1answer
66 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) &...
1
vote
1answer
57 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.
1
vote
0answers
46 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)$ ...
4
votes
1answer
34 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,\...
0
votes
0answers
44 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 ...
3
votes
1answer
54 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 ...
1
vote
1answer
53 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 ...
3
votes
1answer
211 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 ...
0
votes
0answers
131 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| ...
1
vote
1answer
45 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) ...
3
votes
3answers
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 ...
2
votes
0answers
29 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 ?
0
votes
0answers
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 ...
0
votes
0answers
35 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 $\...
0
votes
0answers
32 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, ...
0
votes
1answer
110 views
An "easy" graph problem I can't solve
The question is:
A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2)
And a origin vertex s.
Write an efficient algorithm that finds the ...
3
votes
0answers
31 views
Shortest path which passes through a subset of vertices in an unweighted directed graph [duplicate]
Given an unweighted directed graph $G=(V, E)$, two vertices $s,t \in V$ and a subset of vertices $U \subseteq V$, suggest an algorithm which concludes if there exists a shortest path from $s$ to $t$ ...
0
votes
0answers
21 views
How to close an open polygonal chain such that the resulting enclosed area includes polygon B and excludes polygon C?
I have an algorithmic question for you:
Given: 3D triangle surface mesh, open polygonal chain A, closed polygon B, closed polygon C, all on the mesh.
Wanted: A line that closes A such that B lies ...
0
votes
0answers
30 views
How to close an open polygonal chain in clock- or counterclockwise direction?
I have an algorithmic problem that I am hoping someone can help me out with:
Given: 3D triangle surface mesh, an open polygonal chain (blue).
Wanted: A line that closes the blue line in clockwise ...
3
votes
0answers
113 views
Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work
I am looking for an algorithm to a problem that I encountered when working with 3D modeling:
On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
0
votes
0answers
14 views
Precondition of all-pairs shortest-paths algorithm
In Retiming Synchronous Circuitry , why put a negative sign to d(u) in step 1 ?
Why there is no subtraction operation for W(u, v) in step 3?
1
vote
0answers
47 views
Node disjoint paths with node splitting
I have a not so large network/graph that contains roughly 4000 edges and 1200 different nodes. Each edge has a weight (or cost) and a type (let's say either red or green). Going from one type of edge ...
-1
votes
1answer
34 views
Select the optimal edge to add to a subgraph for minimal the shortest path
The question is as follows:
Let G be connected, directed weighted Graph with non-negative edge weights and let s and t be vertices in G. Furthermore, let K be a subgraph of G with the same number of ...
0
votes
0answers
26 views
How good a center of a BFS tree is?
Consider a graph $G=(V,E)$, and a BFS tree $T$ starting from an arbitrary node $v\in V$.
Now consider finding the center node $u_T$ of $T$, i.e., the vertex with the lowest eccentricity in $T$, which ...
0
votes
0answers
13 views
SMA*+: What if a removed node gets re-generated via another predecessor?
One last question came to me while reading the paper on SMA*+ about setting the $f$-cost of nodes being re-generated.
Well, first, it looks like the part of the algorithm where we set the predecessor ...
2
votes
0answers
18 views
SMA*+: Usefulness of culling heuristics
The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost).
In the benchmark they use a culling heuristic equal ...
2
votes
0answers
18 views
SMA*+: f-cost estimation of re-generated nodes
I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my ...
2
votes
0answers
29 views
Finishing at rest at a target in 2d space
I asked a similar question here, except I forgot to specify that the final velocity must be 0.
I have 2 points in 2D space, start = $s$ and target = $t$, and a starting velocity $v_0$.
At each time ...
1
vote
1answer
19 views
Vector pathing via acceleration with velocity
I'm trying to solve a scenario where I need to find the smallest number of time steps to reach a location in 2d space, where I can manipulate the velocity with an acceleration at each time step where ...
3
votes
1answer
27 views
Shortest path in a grid with turnstile
This question is a simplification of the one about finding the shortest path in a grid with turnstile and waypoints. Since this simplification has dramatic consequences, I think it deserve its own ...
0
votes
1answer
191 views
M + N log N running time for Dijkstra
I'm taking the Design and Algorithms Part -II course in Coursera by professor Tim Roughgarden. In one of the classes, he mentioned that the running time for Dijkstra is $O(m \log n )$ using the heap ...
0
votes
1answer
85 views
Prove Edited Algorithm of Bellman–Ford?
Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.
I am stuck on this question for a week and hope to get some ...
7
votes
3answers
171 views
Shortest walk in a grid with turnstiles and waypoint
This video shows a grid maze with a type of tile that I'd call turnstiles.
The mechanics of those tiles are described below.
A turnstile tile has two bars on adjacent sides of the tile.
You cannot ...
1
vote
1answer
20 views
Algorithm for shorthest path that contains exactly n edges of weight 2 in 1,2-weighted directed graph
I am trying to find an efficient algorithm for the following problem:
Input:
weighted directed graph G=(V, E) in which all edges are weigthed either 1 or 2
s,t ∈ V
n ∈ N
Output
shortest path from s ...
0
votes
0answers
63 views
How (or why) do i find negative cycles with Johnson's algorithm
The first step of Johnson's algorithm is the creation of a new vertex s which has an edge to every other vertex with a weight of 0.
Then I perform only one iteration of the Bellman-Ford algorithm on ...
1
vote
2answers
98 views
Linear program for min-length pair of edge-disjoint paths problem
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, ...
2
votes
1answer
386 views
Shortest path given correct order of colours?
I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c_{1}, ...
1
vote
1answer
36 views
Algorithm for finding strongest connection for a user on social network
I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as:
Problem 6-1. [30 points] I Can Haz Moar Frendz?
Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a ...
0
votes
2answers
86 views
Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?
I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem.
For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with ...
