Questions tagged [shortest-path]

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

Filter by
Sorted by
Tagged with
0
votes
2answers
896 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
27 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
64 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
98 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
385 views

Does Floyd–Warshall work on all graphs?

Floyd–Warshall calculates minimum distance between any two vertices in the graph. ...
2
votes
1answer
304 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
58 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
157 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
256 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
279 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
341 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
33 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
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
29 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
91 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
674 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
129 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
182 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
40 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
320 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
128 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
20 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
283 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
366 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
143 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
285 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
868 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
401 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
276 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
778 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 \...
2
votes
1answer
363 views

Applying Johnson's algorithm on undirected graph with negative edge weights

Currently we are discussing applying Johnson's algorithm on undirected graph with negative edge weights. And the graph may contains cycles, but the sum of weights of any cycle is guaranteed to be non-...
0
votes
1answer
40 views

How to prove that a custom iterative algorithm will determine all shortest paths to a graph node?

I'm not sure what the following algorithm does but it seems that it calculates the shortest paths from a node $t$. Initially we're given a graph $G=(V,E)$ with non-negative weights $c(e) \ge0$ for ...
1
vote
1answer
241 views

How to find the minimal path cost from left edge of a grid to the right edge using dynamic programming?

I need to find the minimal path cost from left edge of a $n\times n$ grid to the right edge where each node has some non-negative weight $cost(i,j)$. $i$ represents horizontal coordinates while $j$ ...
7
votes
4answers
1k views

Check if there is only one simple path in graph between nodes x and y`

Let's say we have given simple undirected graph $G$ having $N$ nodes and $M$ bidirectional edges. For given $x$ and $y$ we want to check if in the graph there is only one simple path between them. ...
2
votes
2answers
980 views

Does the A* algorithm visit every node?

I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, ...
0
votes
0answers
150 views

What would Dijkstra's shortest path algorithm complexity be with the following data structure?

Considering $n$ number of pieces of data, what would Dijkstra's shortest path algorithm time complexity be if it was stored using a data structure with following properties? • delete the record ...
0
votes
0answers
59 views

What is the most efficent single-source shorthest path algorithm in unweighted directed grid graph?

As regards the topic. Here is an example of such a graph:
0
votes
1answer
74 views

Dijkstra algorithm step in Introduction to Algorithms

In the introduction to algorithms proof of Dijkstra, I don't understand why the statement "both y and u were in V-S when u was chosen". We add x before y, and so we relax d[y] with the the edge $$\...
4
votes
1answer
515 views

Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

This is from CLRS problem 24.3-5: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$ . Give ...
1
vote
1answer
179 views

Increasing every starting edge by a constant, then the shortest path tree remains the same?

Consider a directed graph G = (V,E) with non-negative costs on each edge. With s being a starting vertex. Prove that by adding ...
2
votes
0answers
318 views

Algorithm - True shortest path for triangulated 3d-surface

I need to find true shortest path between two points. true means that shortest path can be laid both through the vertices, and through the edges. Input Set of triangles, given by coordinates of 3D-...
1
vote
1answer
547 views

Routing algorithm for train network

I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges ...
-3
votes
1answer
1k views

Best heuristic for A*? [closed]

I'm trying to build a maze solver using A* algorithm. The maze is a grid with movement allowed in 4 directions (up, down, left, right). If there's a starting cell (x1, y1) and a destination (x2, y2), ...
0
votes
2answers
403 views

Questions on shortest path and minimum spanning tree

T/F Questions Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Solution - False I think this should be True, as Dijkstra's Algorithm ...
-1
votes
1answer
389 views

Finding multiple shortest path trees from an undirected, weight graph

In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree. How do I find an ...
0
votes
1answer
218 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 ...
2
votes
1answer
183 views

Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph

Is there any efficient algorithm to find shortest distance between all pairs of vertices? The graph is: Cyclic Sparse (each vertex has either 2 or 3 edge) undirected(bidirectional) weighted non-...
2
votes
1answer
602 views

Single pair shortest path algorithm with time a constraint

I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional ...
4
votes
0answers
582 views

A good heuristic for 2D Rubik's cube

I am looking for a good heuristic function for solving a 2D $n\times n$ Rubik's cube using A* search. There is a game already in the play store. The rules of the game: Swiping LEFT means the ...