Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
653
questions
0
votes
1
answer
34
views
Coding the labyrinth solver
The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473
To summarize, in an unknown strongly ...
- 176
0
votes
3
answers
1k
views
Dijkstra's shortest path algorithm without relaxation
Although I have found a very similar question to what I want to ask here (https://codereview.stackexchange.com/questions/96064/dijkstras-algorithm-without-relaxation), yet I didn't find a satisfactory ...
0
votes
1
answer
109
views
Minimum number of skips needed for shortest path
In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $\leq W$. In our given graph there is no such path but we have the ...
CommunityBot
- 1
0
votes
1
answer
240
views
MIT 6006 Quiz 2: The shortest path task
I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course.
The main idea of creating ...
CommunityBot
- 1
0
votes
0
answers
8
views
Profitable sequence in a $k$-partite DAG
This question is an extension of this one.
Let
$D(V, A)$ be a $k$-partite DAG;
$P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\...
0
votes
1
answer
38
views
Longest path of directed graph with cycle and now weights
If you have a unweighted directed graph with possible cycles, what algorithm would you use to find the longest path without visiting the same node twice? Also, there are multiple starting nodes...
The ...
CommunityBot
- 1
1
vote
1
answer
38
views
Shortest paths in $k$-partite DAG
Let
$D(V, A)$ be a $k$-partite DAG;
$P = \{ p_k : 1 \leqslant k \leqslant |P| \}$ such that $p_k \cap p_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup_{1 \leqslant k \leqslant |P|} p_k = V$ ...
- 15.5k
0
votes
1
answer
442
views
How to deal with cost variation in a dynamic graph when applying Dijkstra
What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
CommunityBot
- 1
0
votes
1
answer
1k
views
Find a path that contains specific nodes without back and forward edges
I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
CommunityBot
- 1
1
vote
1
answer
307
views
A pathfinding algorithm for graphs in which arc weights can change over time
So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction.
Here's the situation, I have a weighted undirected ...
CommunityBot
- 1
0
votes
1
answer
56
views
Shortest path problem with multiple objectives
I would like to solve a shortest path problem on a graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$, which comes to minimize :
\begin{equation}
\label{eq:1}
\underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\...
CommunityBot
- 1
0
votes
1
answer
75
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 ...
CommunityBot
- 1
1
vote
1
answer
34
views
Dynamic Programming as DAGs - Solution Always Shortest Path?
I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the ...
D.W.♦
- 159k
0
votes
1
answer
367
views
Using A* path finding is giving me inaccurate results
So I am using A* pathfinding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of ...
CommunityBot
- 1
1
vote
0
answers
20
views
Admissible Heuristic wiki
I couldn't understand the following part on admissible heuristic on wiki.
How does it reach that they have to be equal? Admissible heuristic only says the eval needs to be equal/less than the true ...
- 11
0
votes
1
answer
149
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). ...
CommunityBot
- 1
1
vote
1
answer
102
views
Implementation check for Kruskal's algorithm used for maze generation
I have a pathfinding project and I want to use Kruskal's algorithm as a maze generator. I am using a rank-based disjoint set data structure to detect cycles, which seems to be the standard way.
...
CommunityBot
- 1
1
vote
2
answers
176
views
How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path
I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, ...
CommunityBot
- 1
1
vote
1
answer
709
views
Minimum distance of nodes from a set of two nodes
In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
CommunityBot
- 1
2
votes
1
answer
56
views
Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?
Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of ...
- 6,157
3
votes
3
answers
774
views
Can the loops be in any order in the Floyd-Warshall algorithm?
I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:
...
- 656
3
votes
1
answer
518
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 ...
CommunityBot
- 1
4
votes
1
answer
97
views
Conditional lower bounds on the running time of the single source shortest path problem
Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
CommunityBot
- 1
1
vote
0
answers
198
views
The second shortest path on a directed graph [closed]
The question asks to write an algorithm using Dijkstra's algorithm with time complexity of
$\Theta(|E| \log |V|)$ that find the second shortest path between $s∈V$ and $t∈V$.
The farthest I managed to ...
- 656
10
votes
3
answers
3k
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 ...
- 16.1k
0
votes
0
answers
28
views
Distance to specific node incremental addition
Let us say I have an empty graph G and a list of nodes N to add to the graph one-by-one. Let us say that I will have a node <...
- 101
0
votes
1
answer
181
views
Shortest Hamiltonian Path in a Complete Graph
I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm ...
- 837
0
votes
2
answers
448
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/...
D.W.♦
- 159k
-2
votes
2
answers
208
views
Could this novel algorithm be qualified to be published in Nature or Science
I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
0
votes
0
answers
21
views
JPS-like path finding algorithm that keeps a distance from the obstacles?
I am using the JPS algorithm to find the shortest path from start $S$ to goal $G$ on a binary grid where each cell can be eithe 0 (free) or 1 (obstacle). Now, I would like my algorithm to take into ...
- 101
0
votes
0
answers
59
views
Lookup Using Path Matrix in Floyd Warshall Algorithm
How is the path matrix created by the Floyd Warshall algorithm used for path lookup?
The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
0
votes
0
answers
34
views
Probabilistic Pathfinding
Here an interesting graph problem I've recently saw:
After a heist in New York City, a group must reach Miami within a set timeframe to catch an escape boat. Their vehicle's GPS shows U.S. routes with ...
- 1
0
votes
1
answer
106
views
find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)
We have a weighted and undirected graph.
I want to find the shortest path between two vertices with Dijkstra algorithm.
But in the path, the weight of the edges should be increased and decreased one ...
CommunityBot
- 1
1
vote
1
answer
222
views
Question about step in proof that predecessor subgraph forms a breadth-first tree
Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:
Theorem 22.5: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, ...
- 36
29
votes
3
answers
15k
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 ...
- 6,157
1
vote
0
answers
224
views
State-of-the-Art techniques on dynamic shortest path computations
Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target ...
- 6,157
1
vote
0
answers
45
views
How to compute the updated shortest paths given a set of edge insertions efficiently?
Let $G = (V, E)$ be a graph with edge weights $w: E \rightarrow \mathbb{R} \cup \{\infty\}$.
Let $P := \{(a_i, b_i, w_i)\}$ be a set of tuples of nodes $a_i, b_i \in V$ with shortest distance $w_i$ ...
- 6,157
3
votes
1
answer
3k
views
Shortest path with a start vertex that touches all nodes at least once with repeats allowed
I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I ...
0
votes
0
answers
39
views
Running time of variant of Dijkstra's algorithm
Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
- 286
1
vote
0
answers
415
views
Can the shortest path problem be solved using Monte Carlo Tree Search?
I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step.
If we consider the path ...
CommunityBot
- 1
1
vote
1
answer
138
views
Solving shortest path with negative weights with linear program. What is the underlying problem we want to solve?
Let us consider a shortest path problem with weights $w_e$ for each edge $e$. It can be formulated as a (integer) linear program (ILP).
\begin{align}
\min \quad &\sum_{e \in E} w_e x_e \\
s.t. \...
- 6,157
1
vote
1
answer
129
views
Finding shortest path between two points in a polygon whose vertices are given?
A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
- 6,157
0
votes
0
answers
19
views
k-shortest paths with iso-timing constraint
I would like to solve the $k$ shortest paths on a directed graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$ :
\begin{equation}
\label{eq:1}
\underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\sum_{(i,j)\in\...
- 51
1
vote
1
answer
164
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....
CommunityBot
- 1
4
votes
2
answers
225
views
Single Source Shortest Path Problem with Multiple Weights Each Edge
I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p ...
D.W.♦
- 159k
0
votes
0
answers
18
views
Importance of an edge regarding distances
Given a graph $G=(V,E)$ and any edge $(u,v) \in E$, let us denote by $G_{(u,v)}=(V,E\setminus\{(u,v)\})$ obtained from $G$ by removing this edge.
I am interested in the difference between the average ...
- 634
2
votes
0
answers
18
views
Inverted Min Cost Max Flow
I'm starting to think there's no possible solution to this problem, but before jumping to conclusions I want to confirm it with collective knowledge.
Let's imagine that there's a 2D grid, where S ...
1
vote
0
answers
31
views
Is Dijkstra's algorithm used in cheapest airfare calculators?
Is Dijkstra's shortest-path graph algorithm used in cheapest airfare calculators like Expedia or CheapAir?
- 148
1
vote
0
answers
110
views
Finding the shortest path with Bellman-Ford [duplicate]
I feel this is a basic question but have been stuck at this for days. Consider an undirected graph with positive weights on its edges. The goal is to find is to get the shortest path between any two ...
D.W.♦
- 159k
1
vote
1
answer
31
views
Route planning on line segments which can be connected or not
I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am ...
- 111