Questions tagged [shortest-path]

Questions about the algorithmic problems of finding shortest paths between nodes in a graph.

Filter by
Sorted by
Tagged with
5
votes
1answer
270 views

Shortest path when allowed to reverse an edge

We're given an unweighted directed graph with vertices $V$ and edges $E$. We're trying to find the shortest path from $s$ to $t$ but we're allowed to travel along up to one edge in the ...
2
votes
0answers
110 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 (...
2
votes
4answers
2k 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
31 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 ...
1
vote
1answer
75 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
163 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
1answer
123 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
116 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 ...
3
votes
1answer
430 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
76 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
1k 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
124 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
61 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
24 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
100 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
855 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 ...
1
vote
1answer
268 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
42 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
116 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
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
0answers
39 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
107 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
122 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
1answer
505 views

Does Floyd–Warshall work on all graphs?

Floyd–Warshall calculates minimum distance between any two vertices in the graph. ...
2
votes
1answer
369 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 ...
2
votes
0answers
60 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
233 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
350 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
329 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
412 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
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 ...
2
votes
0answers
36 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 ...
2
votes
1answer
1k 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
34 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
123 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
809 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
152 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
208 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
41 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
424 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
129 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
22 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
336 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 ...
2
votes
1answer
448 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
172 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
331 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
1k 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
629 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 ...
2
votes
1answer
337 views

Conditional Shortest Path Through Weighted Cyclic Directed Graph

Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge ...
3
votes
2answers
1k views

The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm

In the Floyd-Warshall algorithm we have: Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to $j$ for which all intermediate vertices are in the set $\{1, 2, \cdots, k\}$ then \...