Questions tagged [shortest-path]
Questions about the algorithmic problems of finding shortest paths between nodes in a graph.
552
questions
1
vote
1answer
181 views
Minimum bottleneck path between two vertices in an undirected graph
I have an undirected graph, where the value of the path is the maximum weight among all weights
edges included in it. And I want find the path of minimum value between two given vertices in time $O(n ...
1
vote
1answer
33 views
Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria
I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week.
For N ...
1
vote
1answer
39 views
calculating a shortest path in a table structure that changes in real time
I have a table that looks like this
In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user.
In any moment the player ...
1
vote
1answer
456 views
Shortest path in a incomplete graph
I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
1
vote
1answer
56 views
Is the number of shortest paths between every two vertices at most 4*n^3?
In every weighted graph with $n$-vertices
with negative weights,
with $n > 10$,
a weight can't appear $n$-times in graph,
there are between every two vertices at most $4n^3$ shortest paths.
I'm ...
1
vote
1answer
72 views
Combinatorial Optimization: Shortest distance given sets of drivers and riders
Problem:
I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to ...
1
vote
1answer
62 views
Shortest path in graph by flipping binary colored nodes to one color [closed]
Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the ...
1
vote
1answer
117 views
Will MST find the shortest path for each pair $(r,v)$?
Will local best choice will lead to global best choice? In other words, I'm thinking about whether it's possible that the MST has to put its branch location in the middle of two far nodes ...
1
vote
1answer
477 views
Word ladder problem for words with different length
Is there some one who know any algorithm for word ladder problem with words of different length?
Actually we have some strings with same length and some strings with one length longer but not from ...
1
vote
1answer
2k views
Dijkstra’s shortest path algorithm
I'm learning about single source shortest path algorithms and need to clarify few doubts-
Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers.
Does ...
1
vote
1answer
187 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
185 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
1answer
2k 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
1answer
84 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
1answer
194 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 ...
1
vote
1answer
128 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, ...
1
vote
1answer
505 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 ...
1
vote
1answer
442 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
1answer
488 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$ ...
1
vote
1answer
388 views
Find minimum time path between two nodes
I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers.
A graph with Vertices representing charges and Edges representing distances ...
1
vote
1answer
77 views
Movement on Labyrinth with Best First Search
I have the following labyrinth where R is the robot(the parent node), red blocks are the obstacles where the R cannot move and <...
1
vote
1answer
310 views
Shortest path tree from each vertex implies a unique MST?
Given a connected, undirected graph G, edge-weighted (positive), prove that
If G has a spanning tree T which, for each vertex r in G, is a shortest path tree from r, then G has a unique MST.
I know ...
1
vote
2answers
245 views
Sum of all distances in connected DAG in $O(n\log n)$
I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows: For every node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are ...
1
vote
1answer
65 views
Shortest past including an edge from a given set
I am working on the following problem.
There are N vertices and M roads connecting them. Some of the roads are broken. I have to go from vertex 1 to vertex N taking at least one good road and find ...
1
vote
1answer
881 views
Correctness of Dijkstra's algorithm
This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661).
The proof makes a case that considering path $...
1
vote
2answers
555 views
modify Dijkstra's algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex
i want to modify Dijkstra algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex
I tried it with BFS(breadth first search). Initially ...
1
vote
1answer
949 views
Algorithm to find a path connecting given nodes in a graph
Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for ...
1
vote
1answer
1k views
Shortest-Path for Weighted Directed Bipartite Graphs
I did a research project in which I seek to move a car through zones from origin to destination. This allows for the formulation of a bipartite graph because only adjacent zones can be connected. Each ...
1
vote
1answer
890 views
Shortest walk that covers $k$ nodes
I have the following problem, I would like to know an efficient algorithm to solve it.
Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex $s$...
1
vote
2answers
456 views
Using Dijkstra to find shortest path in relation to two weight functions?
I'm given a graph and two weight functions, $w_1$ and $w_2$, such that there doesn't exist a negative loop in the graph in $w_1$ and $w_2$. I'm also given two vertices, $s$ and $t$, and am asked to ...
1
vote
2answers
975 views
Finding all paths with lengths in a fixed interval in sparse graphs
What is the most efficient way to find all paths of length M to N in a large sparse graph?
Some general information:
Graph has 30,000 to 50,000 nodes
Average number of edges per node ~ 10
M=4, N=7
...
1
vote
1answer
601 views
Bellman-Ford parent pointer (?) negative cycle
First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof ...
1
vote
0answers
16 views
Can the Bellman-Ford Algorithm be used to find the longest path in an undirected graph through first negating the weight of all the edges? [duplicate]
I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first ...
1
vote
1answer
21 views
How do i make sure i get the correct Bellman Ford path?
I was studying shortest path algorithms and was met with an issue regarding Bellman Ford for the image below.
Following the graph, i see that node 3 has a length of 1 while node 2 has a length of 2. ...
1
vote
0answers
27 views
Dijkstra's algorithm - additional properties
Say we let $R$ denote the set of currently chosen vertices in Dijkstra's algorithm, $d$ be the currently stored path-length estimates, and $s$ be the source. The standard property that we know is true ...
1
vote
0answers
45 views
Proving that every graph has an order such that Bellman Ford can run in one iteration
I need to prove that for every given graph, that doesn't contain negative cycles, there is an order of edges so that Bellman-Ford algorithm will finish running after one iteration.
I could only solve ...
1
vote
0answers
20 views
Solving multiple pathfinding problems efficiently
Let $V$ be a set of nodes, $c : V \times V \rightarrow \mathbb{R} \cup \{\infty\}$ be an edge cost function, and $h : V \times V \rightarrow \mathbb{R}$ be an admissible heuristic. Suppose we want to ...
1
vote
0answers
28 views
Finding homotopies in a 2-complex
Are there any efficient algorithms to find the shortest homotopy between two paths in a $2$-complex?
1
vote
1answer
45 views
How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path
I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, ...
1
vote
0answers
235 views
Johnson's vs Floyd-Warshall for dense graphs
I often read that Floyd-Warshall is a good fit for dense graphs and Johnson's for sparse ones. While it's easy to see why Johnson outperforms Floyd-Warshall on sparse graphs, I'm noticing that ...
1
vote
0answers
16 views
Queries on unbounded knapsack
Given $n$ types of items with integer cost $c_{i}$ (there is an unlimited number of items of each type), such that $c_{i} \leq c$ for all $i = 1, 2, \dots, n$, answer (a lot of) queries of form "is ...
1
vote
1answer
60 views
A pathfinding algorithm for graphs in which arc weights can change over time
So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction.
Here's the situation, I have a weighted undirected ...
1
vote
1answer
30 views
Dijkstra shortest path yields unintuitive results
Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, ...
1
vote
0answers
424 views
Remove a vertex from a graph keeping shortest path distance same
How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.
1
vote
0answers
156 views
C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?
I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments.
The algorithm iterates over every edge in the graph.
...
1
vote
0answers
94 views
Can the shortest path problem be solved using Monte Carlo Tree Search?
I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step.
If we consider the path ...
1
vote
1answer
290 views
Minimum distance of nodes from a set of two nodes
In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
1
vote
0answers
39 views
Concurrent Shortest Paths with “Congestion Penalty”
Given a graph with positive edge weight representing "time to travel through", and 2 or more pairs of start/end vertices, we can find concurrent paths for the pairs such that the maximum cumulative ...
1
vote
1answer
48 views
What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?
The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with ...
1
vote
0answers
263 views
Intuition behind Floyd-Warshall being faster
I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm:
Let $dp[i][j][n]$ denote the shortest path from $...
