Shortest Paths with Non-Negative Edge Weights
Authors: Benjamin Qi, Andi Qu
Introduces Bellman-Ford, Floyd-Warshall, Dijkstra.
Nearly all Gold shortest path problems involve Dijkstra. However, it's a good idea to learn Bellman-Ford and Floyd-Warshall first since they're simpler.
Bellman-Ford
Resources | |||
---|---|---|---|
CPH | up to but not including "Negative Cycles" |
Floyd-Warshall
Focus Problem – read through this problem before continuing!
Tutorial
Resources | |||
---|---|---|---|
CPH | example calculation, code | ||
cp-algo | code, why it works | ||
PAPS | code, why it works | ||
CP2 |
A common mistake in implementing the Floyd–Warshall algorithm is to misorder the triply nested loops (The correct order is
KIJ
). The incorrectIJK
andIKJ
algorithms do not give correct solutions for some instance. However, we can prove that if these are repeated three times, we obtain the correct solutions.It would be emphasized that these fixes (repeating incorrect algorithms three times) have the same time complexity as the correct Floyd–Warshall algorithm up to constant factors. Therefore, our results suggest that, if one is confused by the order of the triply nested loops, one can repeat the procedure three times just to be safe.
Problems
Used as the first step of the following:
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
Gold | Hard | Show TagsAPSP, DP | External Sol |
Dijkstra
Focus Problem – read through this problem before continuing!
The USACO training pages present a implementation, although this is rarely used nowadays.
Resources | |||
---|---|---|---|
cp-algo |
Resources | |||
---|---|---|---|
CPH | code | ||
cp-algo | |||
CPC | |||
CP2 |
Implementation
Resources | |||
---|---|---|---|
Benq |
C++
Recall from the second prerequisite module that we can use greater<>
to make the top element of a priority queue the least instead of the greatest. Alternatively, you can negate distances before placing them into the priority queue, but that's more confusing.
1#include <bits/stdc++.h>2using namespace std;34using ll = long long;5#define pb push_back67vector<pair<int, int>> graph[100000];8// Adjacency list of (neighbour, edge weight)9ll dist[100000];10int N;
Java
1import java.util.*;2import java.io.*;34public class test {5 static class Pair<K, V> {6 public K a;7 public V b;8 public Pair(K a, V b) {9 this.a = a;10 this.b = b;
Warning!
It's important to include continue
. This ensures that when all edge weights are non-negative, we will never go through the adjacency list of any vertex more than once. Removing it will cause TLE on the last test of the above problem!
This section is not complete.
(explanation of hack case)
Can be done in with Fibonacci heap. In practice though, this is rarely faster, since the Fibonacci heap has a bad constant factor.
Problems
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
CSES | Easy | Show TagsSP | ||||
Gold | Easy | Show TagsSP | External Sol | |||
Gold | Easy | Show TagsSP | External Sol | |||
Gold | Easy | Show TagsSP | External Sol | |||
Gold | Normal | Show TagsSP | External Sol | |||
CSES | Normal | Show TagsSP | ||||
Kattis | Normal | Show TagsSP | External Sol | |||
CSES | Normal | Show TagsSP | ||||
IOI | Hard | Show TagsSP | External Sol | |||
JOI | Hard | Show TagsSP, DP | ||||
APIO | Hard | Show TagsSP, Geometry | ||||
Balkan OI | Hard | Show TagsSP | ||||
Balkan OI | Very Hard | Show TagsSP, Monotone stack | View Solution |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!