Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
496
questions
1
vote
1answer
524 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 ...
1
vote
0answers
11 views
Queries on unbounded knapsack
Given $n$ types of items with integer cost $c_{i}$ (there is an unlimited number of items of each type), such that $c_{i} \leq c$ for all $i = 1, 2, \dots, n$, answer (a lot of) queries of form "is ...
1
vote
0answers
15 views
Finding multiple paths through a grid such that every grid square is equally used
Setup
Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
1
vote
1answer
28 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 ...
1
vote
1answer
28 views
Dijkstra shortest path yields unintuitive results
Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, ...
1
vote
0answers
144 views
Remove a vertex from a graph keeping shortest path distance same
How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.
1
vote
0answers
120 views
C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?
I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments.
The algorithm iterates over every edge in the graph.
...
1
vote
0answers
47 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 ...
1
vote
1answer
158 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, ...
1
vote
0answers
39 views
Concurrent Shortest Paths with “Congestion Penalty”
Given a graph with positive edge weight representing "time to travel through", and 2 or more pairs of start/end vertices, we can find concurrent paths for the pairs such that the maximum cumulative ...
1
vote
1answer
44 views
What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?
The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with ...
1
vote
1answer
1k views
Behaviour of Dijkstra in Case of Negative Edge Weight [duplicate]
I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss.
For the given below graph
What should be the Cost to reach Node G from Source Vertex ...
1
vote
0answers
52 views
Finding simple min-weight path between two vertices in graph with negative edge weights
Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$...
1
vote
0answers
133 views
Minimizing cost of shortest paths to a group of vertices by adding minimal edges to an unconnected vertex
Let $G=(V,E)$ be directed graph, where the weights of the edges are non-negative. The graph might have cycles, but without parallel edges.
Consider a $T \subset V$, and $u \notin V$.
I'm trying to ...
1
vote
0answers
210 views
How to handle negative edge weights in distance vector routing protocol with a digraph?
In a Distance Vector routing protocol each node implements a Bellman-Ford inspired algorithm that shares it's routing table (Distance Vector) with each of it's incoming links (upstream neighbors). ...
1
vote
0answers
22 views
Why does the inequality $d[v_i] \ge d[v_i−1] + w(v_i−1, v_i)$ hold when all vertices are labelled with their shortest path values upon?
Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \to R$, and let $s \in V$ be a source vertex. Assume that G does not contain a negative cycle reachable from $s$. Then, if we ...
1
vote
0answers
23 views
Shortest curve interpolating points with a constraint on the curvature
I'm looking for a method for determining a path for a UAV that interpolates a set of input locations, with a constraint on maximum curvature and given an initial velocity vector.
The cost (length) of ...
1
vote
1answer
421 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 ...
1
vote
0answers
295 views
Analysing Dijkstra Algorithm by using different varieties of Data Structure
Question
I want to analyse Dijkstra Algorithm by using different varieties of Data Structure.
My solution
Adjacency matrix to Store the Graph and Binary heap for Priority Queue.
$...
1
vote
0answers
49 views
DAG Shortest Path — original citation for academic paper
I am writing to see if someone can point me to the original citation (assuming that a single work can be pointed to) for the single-source shortest path problem in directed-acyclic graphs (DAGs). ...
1
vote
0answers
354 views
Shortest path with minimal blue edges
Let $G=(V,E)$ be an undirected graph,such that ever $e\in E$ has a color-blue or red.
Given $G$ and some $s,t\in V$ ,find an efficient algorithm that find from all pathes from $s$ to $t$,one with ...
1
vote
0answers
2k views
How to backtrack the shortest path in BFS based shortest path calculation? [closed]
I understand how BFS can give the shortest path in a graph but I am not able to code the entire thing. The part where I am stuck is when I pop a node from the queue and see that its the target node, ...
1
vote
0answers
54 views
Pathfinding when the graph varies over time
Let's say I want to simulate a very large number of travelers booking flights. For example, a traveler might want to fly from New York to New Delhi. There's no direct flight from New York to New Delhi,...
1
vote
0answers
591 views
Edge weight changing during execution in shortest path algorithm
I have an undirected graph with weighted edges, in which I want to find the shortest paths from an initial node to every other node. Obviously Dijkstra's algorithm is usually a good choice, and I have ...
1
vote
0answers
164 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 ...
1
vote
1answer
509 views
Bellman-Ford: Find all nodes that have minus infinite distance to source
Given a weighted, directed graph (V, E) may contains some negative cycles and a source node s, I would like to know for all node ...
1
vote
0answers
803 views
Correctness of Dijkstra's algorithm
This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661).
The proof makes a case that considering path $...
1
vote
0answers
17 views
Optimal linking in synchronous environment for shortest path tree problem
I am dealing with the Shortest path tree problem in the specific synchronous environment.
In the following algorithm, initiator begin the execution calling primitives ...
1
vote
0answers
112 views
How do I apply a single iteration of Floyd's algorithm to an adjacency matrix? [closed]
I have the following adjacency matrix for a graph with nodes {a,b,c,d}:
\begin{bmatrix}
& & a& b& c& d\\
& & & & & \\
a& & 0& 1&...
1
vote
0answers
23 views
Finding next lightest path [duplicate]
Using Dijkstra algorithm, how can I find the next shortest path in a directed weighted graph? (When saying next, I mean that the next path must be heavier than the lightest path and not equal). The ...
1
vote
0answers
130 views
Weighted, Acyclic Graph and Change Weights Problem?
I ran into a question as follows:
We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with ...
1
vote
0answers
103 views
Fully dynamic k-shortest-path
I have a directed acyclic graph with positive edge weights. It is constantly changing in that nodes are deleted and added. For each change, I need to find the $k$ shortest paths.
My current approach ...
1
vote
0answers
56 views
How to convert a search solution to a path to be tracked?
Let's say I have a space with obstacles and I'm trying to control a robot's movement while avoiding obstacles. I also have a start state and a goal state. I use a search algorithm to find the shortest ...
1
vote
1answer
766 views
find the shortest path between two nodes where the number of edges is minimal [closed]
Say you are given an undirected unweighted graph, where s and t are nodes from the graph.
d(s,t) means the distance between s and t which outputs the number of edges.
How do I find the the maximum ...
1
vote
0answers
352 views
Influence of edge number and priority-queue implementation on the runtime of Dijkstra
When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
1
vote
0answers
452 views
Parallel single source shortest path algorithm
Is there a deterministic parallel single-source shortest path algorithm (for graphs with non-negative edge-weights) that runs in sublinear time? The number of processors may depend on $n$ or $m$ (i.e.,...
1
vote
0answers
93 views
Shortest path with min-sum multiplication and Boltzmann distribution
My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution.
He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann ...
1
vote
2answers
134 views
Shortest path with a given condition
The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two ...
1
vote
1answer
322 views
Find shortest path in undirected graph that goes through all vertices and returns to starting vertex
I have an undirected weighted graph like this one
My task is to find the fastest path (with least weight) that goes from specified vertex goes through all vertices and returns to the starting vertex ...
0
votes
2answers
409 views
Can Inverse of weights(1/weight,not negation) be used to find the longest path between two points by using dijkstra's algorithm?
Considering that there no cycles in the graph.
I have seen the posts where the negation of the weights is suggested and to use Bellman-ford. But I was wondering if the inverse is possible.
0
votes
1answer
36 views
Why does A* fail to find the fastest path when it reaches the goal?
I'm trying to understand how A* works on some simple examples, and something struck me as odd. I could fairly easily come up with situations in which A* "failed". Here is an example:
Take a 2x2 grid, ...
0
votes
3answers
832 views
Modification of Dijkstra's algorithm
How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality?
There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough ...
0
votes
2answers
537 views
Existence of shortest path in a graph with no negative cycles?
Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex.
How do I prove that for every ...
0
votes
2answers
662 views
Bellman–Ford negative path meaning
In the Bellman–Ford algorithm, what is the practical meaning of
having a negative path between routers?
I have tried searching the net but didn't find any data
thanks
Eli
0
votes
2answers
4k views
How to construct the found path in bidirectional search
I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (...
0
votes
2answers
282 views
Shortest distance from multiple points to one point
I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the ...
0
votes
2answers
1k views
Shortest path in a maze where you can break one wall
How would I solve the following problem?
You have maps of parts of the space station, each starting at a prison exit
and ending at the door to an escape pod. The map is represented as a
matrix of 0s ...
0
votes
1answer
582 views
Why does Dijkstra's algorithm not account for updating node distances after expanding a node?
Why does Dijkstra's algorithm not re-evaluate/re-expand nodes who have been expanded and later had their weight changed?
For example, in the accepted answer of this question (link), if the algorithm ...
0
votes
1answer
2k views
Normalizing edge weights and the effect on Dijkstra's algorithm [duplicate]
If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would ...
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 ...
