Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
0
votes
0answers
3 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
30 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
14 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
17 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
61 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 ...
1
vote
1answer
32 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
167 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
101 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
44 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
54 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
577 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
21 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
63 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
61 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
122 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
18 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
19 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
46 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
66 views
Does Floyd–Warshall work on all graphs?
Floyd–Warshall calculates minimum distance between any two vertices in the graph.
...
2
votes
1answer
65 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
26 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
36 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
75 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
60 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
100 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
20 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
23 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
22 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
117 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
52 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
257 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
35 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
97 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$ ...
3
votes
0answers
38 views
Defining preferred paths makes $A^*$ heuristic lose admissibility
In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to ...
0
votes
1answer
93 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 ...
4
votes
1answer
126 views
Given an oriented graph, return true if paths have a specified length
I'm having trouble solving this exercise about graphs, I hope you can help me:
Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an ...
1
vote
0answers
19 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
58 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 ...
3
votes
1answer
135 views
Avoiding loops in Bellman-Ford algorithm
If you apply standard Bellman-Ford algorithm to a graph containing negative loop it can only report its existence. Are there approaches to modify it to find shortest path containing any vertex not ...
0
votes
0answers
52 views
Applicability of Dijkstra's algorithm to hypergraphs
When I search for Dijkstra's algorithm and hypergraphs, I don't get any results discussing it. The Wikipedia page regarding Dijkstra's algorithm doesn't mention hypergraphs and the one regarding ...
1
vote
1answer
83 views
weight constrained shortest path problem variants
Given a graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:E\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ ...
1
vote
2answers
435 views
Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms
The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford ...
1
vote
1answer
131 views
Hamiltonian path and minimum spanning tree
Suppose i have a graph and i want to find minimum-spanning-tree. As in imperative languages we have to take specific steps from everynode(example ,we use kruskal's algorithm or prim's algorithm) to ...
