PrevNext
Somewhat Frequent
 0/16

Shortest Paths with Non-Negative Edge Weights

Authors: Benjamin Qi, Andi Qu, Qi Wang

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
CPHup to but not including "Negative Cycles"

Floyd-Warshall

Focus Problem – read through this problem before continuing!

Tutorial

Resources
CPHexample calculation, code
cp-algocode, why it works
PAPScode, why it works
CP2
Optional: Incorrect Floyd-Warshall

Paper

A common mistake in implementing the Floyd–Warshall algorithm is to misorder the triply nested loops (The correct order is KIJ). The incorrect IJK and IKJ 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:

StatusSourceProblem NameDifficultyTagsSolutionURL
GoldHard
Show Tags

APSP, DP

External Sol

Dijkstra

Focus Problem – read through this problem before continuing!

O(N2)\mathcal{O}(N^2)

The USACO training pages present a O(N2)\mathcal{O}(N^2) implementation, although this is rarely used nowadays.

Resources
cp-algo

O(MlogN)\mathcal{O}(M\log N)

O(MlogN)\mathcal{O}(M\log N) 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.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
vector<pair<int, int>> graph[100000];
// Adjacency list of (neighbour, edge weight)
ll dist[100000];
int N;

Java

import java.util.*;
import java.io.*;
public class test {
static class Pair<K, V> {
public K a;
public V b;
public Pair(K a, V b) {
this.a = a;
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 case of the above problem!

The last test case contains 100000 destinations and 149997 flights. City 1 has flights to cities 2 through 50000. Cities 2 through 50000 have flights to city 50001. City 50001 has flights to cities 50002 through 100000. Without the continue, after the program pops cities 1 through 50000 off the queue, the priority queue will contain 49999 routes that end at city 50001. Every one of the 49999 times city 50001 is popped off the queue and processed, we must iterate over all of its outgoing flights (to cities 50002 through 100000). This results in a runtime of Θ(N2logN)\Theta(N^2\log N), which will TLE.

On the other hand, if we did include the continue, the program will never iterate through the adjacency list of city 50001 after processing it for the first time.

Optional: Faster Dijkstra

Can be done in O(M+NlogN)\mathcal{O}(M+N\log N) with Fibonacci heap. In practice though, this is rarely faster, since the Fibonacci heap has a bad constant factor.

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

SP

GoldEasy
Show Tags

SP

GoldEasy
Show Tags

SP

External Sol
GoldEasy
Show Tags

SP

External Sol
GoldNormal
Show Tags

SP

External Sol
CSESNormal
Show Tags

SP

KattisNormal
Show Tags

SP

External Sol
CSESNormal
Show Tags

SP

IOIHard
Show Tags

SP

External Sol
JOIHard
Show Tags

SP, DP

APIOHard
Show Tags

SP, Geometry

Balkan OIHard
Show Tags

SP

Balkan OIVery Hard
Show Tags

SP, 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!

Give Us Feedback on Shortest Paths with Non-Negative Edge Weights!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext