Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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$ ...