Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
1
vote
1answer
35 views
Calculate Shortest Path (Shortest Time) Through a Store in a Graph
There is an undirected graph and some of the vertices are said to be stores.
Person A wants to reach to person B with a present. That means person A has to stop by one of the vertices marked as stores ...
1
vote
1answer
47 views
Find shortest path for a volatile graph
Let me define a volatile graph first:
It is an undirected graph in which the weight of each
edge varies every time we query it. That is, when we request the weight
w(e) of edge e, we obtain an ...
1
vote
0answers
30 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$...
0
votes
1answer
21 views
Confirmation of alternative correctness proof for Floyd-Warshall's all-pair shortest-path algorithm
The most common proof for Floyd-Warshall's algorithm is an induction proof on the outer-most loop, which says
$\delta^k(i,j)=\begin{cases}
\min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\}...
1
vote
0answers
34 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 ...
0
votes
0answers
23 views
BFS better performence
I got the undirected unweighted graph. Where every node represents one city. Every city produces one type of grocery (does not have to be unique).
Then you will have on the input a number of type ...
1
vote
1answer
71 views
Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?
Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
4
votes
1answer
72 views
Given a directed graph, allowed to reverse one or zero edges to make shortest path from S to T
I googled and couldn't find something similar, thanks for your attention and help.
EDIT:
Thanks for your feedback. Now I try to be more clear.
Given a directed graph with $V$ vertices and $E$ edges....
2
votes
0answers
41 views
Shortest route through ordered points
My algorithm-fu is really weak and I do not know how to express following problem in terms of any other problem known to me:
Given a small rectilinear grid and coordinates of four cells in this grid (...
1
vote
3answers
183 views
Chess Knight minimum moves to destination on an infinite board
There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm.
Here is ...
2
votes
1answer
25 views
Travelling Problem with Constraints
Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.
You start your travel at a given node, say $1$, and end ...
0
votes
1answer
36 views
How do I solve a maze using velocity and acceleration?
I need to solve a maze. I can move an object around in a 2D maze by giving it 1 acceleration in any 8 of its 8 directions.
The object starts at rest at 0 velocity.
By only adding an acceleration at ...
1
vote
0answers
34 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). ...
0
votes
0answers
25 views
Long simulation times due to high dimensions shortest path problem
In my economics research I am using a shortest path algorithm (see Shortest path from one source which goes through N edges). However, the algorithm works only for few number of nodes and edges, and ...
1
vote
1answer
22 views
Recursive DP vs Graph Traversal solutions to path-based problems
I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can ...
3
votes
2answers
72 views
Is there a solution for this maze problem in polynomial time?
Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now ...
2
votes
1answer
58 views
Modifying Floyd–Warshall Algorithm for Vertex Weights
I was trying to modify the Floyd–Warshall's algorithm to take into account the weights over the vertices, in addition to the weight of the edges, while computing the shortest path. The length of a ...
1
vote
1answer
37 views
Shortest path in a graph where edges are forbidden depending on the path taken
I have a problem similar to Shortest path problem where edge weight depends on path taken but not quite the same. In my case each edge has either a fixed finite weight, or an infinite weight, ...
4
votes
1answer
431 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 ...
2
votes
0answers
105 views
Shortest path from one source which goes through N edges [closed]
In my economics research I am currently dealing with a specific shortest path problem:
Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from ...
2
votes
1answer
45 views
How to find MST for each source
Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost.
The image bellow is an example of a possible ...
0
votes
0answers
18 views
Implementation/explanation of the hub based labelling algorithm
I've found plethora of papers describing the performance advantages and basic correctness proofs of the hub-based labelling shortest path algorithm.
However I'd like to implement the algorithm, and ...
2
votes
2answers
58 views
Shortest travelling cost if we have bunch of points in 2D plane
I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
6
votes
2answers
585 views
Finding the most efficient paths to cover an area from multiple starting locations
I'm looking to design an algorithm for a problem I have, and was hoping there may be someone that could provide some insight on where to start.
In my picture above, the grid is the area they needs to ...
0
votes
0answers
23 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.
...
1
vote
1answer
66 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 ...
2
votes
1answer
33 views
Comparing nodes in A*
Nodes in the open list in A* will be sorted by their f-cost, but if the f-cost of two nodes are equal, will their h-costs instead be compared? I'm asking because I've seen implementations where the h-...
2
votes
1answer
65 views
LPA* implementation keeps looping
Short story
I am currently trying to implement LPA* in an existing navigation system and find the algorithm seems to loop forever, expanding the same vertices over and over again. I am wondering what ...
0
votes
2answers
265 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
0answers
20 views
Balancing Steiner trees with Shortest Path trees
I'm working on a problem that combines Steiner Trees and Shortest Path trees. We have a (sparse, connected) graph $G=(V,E)$ with non-negative edge weights and edge lengths, a set of terminals $T \...
1
vote
1answer
29 views
In LPA*, how are predecessors/successors of a vertex defined?
While trying to implement LPA* (mostly based on its description in the same authors’ paper on its derivative D*Lite), I noticed it mentions predecessors and successors of a vertex without giving a ...
0
votes
0answers
53 views
Shortest path between 2 nodes subject to constraints
I am trying to find shortest path between 2 nodes in a graph similar to below:
Each edge has a weight assigned to it. Also, the graph is directional with each edge directing from left to right.
I ...
0
votes
0answers
61 views
Retrieving all pair shortest path of a dynamic graph efficiently
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 ...
0
votes
1answer
132 views
Does Floyd–Warshall work on all graphs?
Floyd–Warshall calculates minimum distance between any two vertices in the graph.
...
2
votes
1answer
110 views
Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms
From my understanding, a problem amenable to a dynamic programming solution has these two properties:
Overlapping Subproblems — The same subcase (a subsection of the overall problem) keeps ...
0
votes
0answers
38 views
Single source shortest Path Algorithm in dynamic graph
In case of dynamic graphs where edges are added only (all edges have positive weight).
Goal: to keep track of the shortest path from the source to the goal node.
Are their any specific conditions ...
2
votes
0answers
35 views
IP algorithm for finding path in graph
Suppose for each positive integer $N$, we have a graph $G_N$ with $N$ vertices labelled $1$ to $N$ (so $\log N$ bits are required to specify a vertex). Suppose we have a PSPACE algorithm to determine ...
0
votes
1answer
53 views
Consistent heuristic and A*
The following graph has consistent heuristic.
An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be ...
1
vote
1answer
90 views
Dynamic All Pairs Shortest Paths algorithm
I heard about the following problem in a competitive programming camp:
Given an undirected weighted graph $G$ with one vertex initially.
Suppose you are given two types of queries:
Add a new vertex ...
2
votes
2answers
111 views
Is there a variant of Dijkstra’s algorithm for partial recalculation?
Suppose the following:
We use Dijkstra’s algorithm to find the shortest route to our destination.
The start node (current vehicle position) keeps changing, i.e. moving towards the destination along ...
2
votes
2answers
182 views
Find the minimum path to every vertex using Bellman-Ford
I was studying the chapter 24 of the CLRS and got to the following question:
24.1-5 $\star$ Let $G=(V,E)$ be a weighted, directed graph with weight function $w : E \rightarrow \mathbb{R}$. Give an $...
1
vote
0answers
21 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 ...
0
votes
0answers
31 views
Dynamic programming - Find shortest sequence of moves in a grid of letters to type a sentence
We have a keyboard-like grid containing letters or other symbols.
We also have a sentence that we would like to write with the grid.
At the beginning the cursor points at the symbol in the top letf ...
2
votes
0answers
23 views
Generating flight path for aerial photography
I need to generate the shortest possible path for aerial photography using a fixed wing unmanned air vehicle (UAV).
The image below shows the area I'm going to search. The white cells are the cells I ...
1
vote
1answer
251 views
Compute single-source shortest paths in O(n+m) time?
I found the following problem in my textbook and I'm having trouble with coming up with a solution. I'm thinking maybe there's a way to improve Dijkstra's algorithm by using a data structure other ...
0
votes
1answer
26 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, ...
3
votes
0answers
59 views
How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?
For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but ...
3
votes
2answers
340 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 ...
0
votes
0answers
46 views
Shortest path on a dynamic multigraph
I wish I knew the correct terminology for the question that I would like to ask, but I don't, so please forgive me if I am not calling the right things by the right names. The practical problem that I ...
0
votes
1answer
109 views
shortest cycle passing through vertices a and b with changeable edge weights
given a weighted undirected graph with $N$ vertices $(N \leqslant 500)$ we start from vertex $S$ and wo go to $M$ and then we go to $T$ and then we return to $S$.
each edge in graph has weight $a_i$ ...
