# Questions tagged [shortest-path]

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

510 questions
Filter by
Sorted by
Tagged with
154 views

### Hitting probability of random walk within given number of steps

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates. What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially? We can ...
103 views

### Path between two vertices in directed graph without cyclic vertices

I have been searching online for some time but I have not found an answer. Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic ...
758 views

### Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
530 views

### Djikstra's algorithm to compute shortest paths using at least k edges

I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s ...
1k views

### Multiple Source Shortest Paths in a weighted graph

In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at ...
89 views

### Minimal paths as solution of a linear program of a special network flow

Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$. We're looking for the shortest ...
182 views

### Finding a negative cycle in a bipartite graph

The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where ...
276 views

### How can an A* algorithm visit all nodes?

Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
231 views

305 views

### Shortest path from source to all vertices, but with some wildcards

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer). You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
58 views

### Djikstra algorithm analysis

My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that? Dijkstra algorithm pseudocode: ...
3k 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 ...
35 views

74 views

### Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...
80 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 ...