# Questions tagged [shortest-path]

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

497 questions
Filter by
Sorted by
Tagged with
165 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 ...
811 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 ...
750 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 ...
249 views

### Largest possible cost of a shortest path in which every edge's length is either -1, 0, or 1

I'm doing an online course in which I'm struggling with the following (multiple-choice) question: Suppose we run the FLoyd-Warshall algorithm on a directed graph $G =(V,E)$ in which every edge's ...
557 views

### Shortest paths when edge weight depends on previous edge

I have a directed graph with non-negative weights on the edges. I can divide the nodes in two "classes", X (roughly 1700 nodes) and Y (~300). I want to collect all the shortest paths from x in X to y ...
219 views

### Shortest Path using at most k colors

I have an edge-colored network, in which edges also have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the ...
417 views

### Shortest paths among two subsets of nodes

Given a directed graph $G = (V, E)$ with all edge weights being non-negative and two disjoint subsets of nodes $S, T \subseteq V$, design an algorithm to find the shortest paths among $S$ and $T$, (...
1k views

### Shortest path with positive edge cycle

When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their ...
104 views

### Prove that every two vertices in graph are connected by a path of some length

I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning. Every node in ...
458 views

### Running Time of naive implementation of Dijkstra's Algorithm

Here is the "naive" implementation of Dijkstra's algorithm that the professor uses: For a directed graph $G = (V,E)$ as input Initialize: $X = \{s\}$ (the vertices processed so far) ...
88 views

### Partial path known in Single source shortest path problem

I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path. If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal ...
2k views

### How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time. But in this case, we can't track actual shortest path with ...
215 views

76 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 ...
153 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 ...
94 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, ...
408 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 ...
348 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})$ ...
326 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$ ...
250 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 ...
75 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 <...
251 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 ...
210 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 ...
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 ...
533 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 ...
812 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 ...
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 ...
786 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$...
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 ...