# Questions tagged [shortest-path]

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

475 questions
Filter by
Sorted by
Tagged with
127 views

### Path on an edge-colored DAG using exactly $k$ colors

I have the following problem: Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$, does there exist a path from $s$ to $t$ using exactly $k$ ...
5k views

### What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?

Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$. What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ ...
308 views

### BFS in K shortest paths

Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes? If so where can it be useful?
528 views

### Why not relax only edges in Q in Dijkstra's algorithm?

Can someone tell me why almost in every book/website/paper authors use the following: foreach vertex v in Adjacent(u) relax(u,v) when relaxing the edges, ...
6k views

### Dijkstra's algorithm for undirected graphs with negative edges

INPUT: "an undirected, weighted graph (negative weights allowed)" Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work? As far as i ...
25k views

### What is the fastest algorithm for finding all shortest paths in a sparse graph?

In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall ...
530 views

### Bellman-Ford: shortest path

my assumption: - we have an undirected graph with only positive edges - the edges are sorted alphabetically:     e.g A-B, A-C, B-D     and e.g not C-A, D-B, A-...
11k views

### Retrieving the shortest path of a dynamic graph

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 ...
29k views

### Getting negative cycle using Bellman Ford

I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name ...
7k views

### Bellman-Ford algorithm - Why can edges be updated out of order?

The Bellman-Ford algorithm determines the shortest path from a source $s$ to all other vertices. Initially the distance between $s$ and all other vertices is set to $\infty$. Then the shortest path ...
9k views

### Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...