Bellman-Ford Floyd-Warshall Tutorial Problem Explanation Implementation Problems Dijkstra Tutorial

\mathcal{O}(N^2)

\mathcal{O}(M\log N)

\mathcal{O}(M\log N)

Implementation Problem Implementation Problems

Somewhat Frequent

0/17

Shortest Paths with Non-Negative Edge Weights

Authors: Benjamin Qi, Andi Qu, Qi Wang, Neo Wang

Introduces Bellman-Ford, Floyd-Warshall, Dijkstra.

Edit This Page

Prerequisites

Bellman-Ford Floyd-Warshall Tutorial Problem Explanation Implementation Problems Dijkstra Tutorial

\mathcal{O}(N^2)

\mathcal{O}(M\log N)

\mathcal{O}(M\log N)

Implementation Problem Implementation Problems

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	13.1 - Bellman-Ford	up to but not including "Negative Cycles"

Floyd-Warshall

Tutorial


CPH	13.3 - Floyd-Warshall	example calculation, code
cp-algo	Floyd-Warshall	code, why it works
PAPS	12.3.3 - Floyd-Warshall	code, why it works
CP2	4.5 - All-Pairs Shortest Paths

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.

Problem

Shortest Routes II

CSES - Easy

Focus Problem – read through this problem before continuing!

Explanation

This problem asks us to compute shortest paths between any two vertices. Hence, Floyd-Warshall is suitable because of the low $N (N \le 500)$ , and the inclusion of negative weights.

Implementation

Time Complexity: $\mathcal{O}(N^3)$

C++

 Code Snippet: C++ Short Template (Click to expand)

ll INF = 1e18;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;

Java

import java.io.*;
import java.util.*;


public class Main {
 	Code Snippet: Kattio (Click to expand)

	public static void main(String[] args) {
		Kattio io = new Kattio();

Problems

Used as the first step of the following:

Status	Source	Problem Name	Difficulty	Tags
	Gold	Moortal Cowmbat	Hard	Show Tags APSP, DP

Dijkstra

Tutorial

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

Resources
	cp-algo	Dijkstra (Dense Graphs)

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


CPH	13.2 - Dijkstra	code
cp-algo	Dijkstra (Sparse Graphs)
CPC	8 - Shortest Paths
CP2	4.4.3 - SSSP on Weighted Graph

$\mathcal{O}(M\log N)$ Implementation

Resources
	Benq	Dijkstra

Problem

Shortest Routes I

CSES - Easy

Focus Problem – read through this problem before continuing!

Implementation

Time Complexity: $\mathcal{O}(N + M\log N)$

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 $\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 $\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

Source	Problem Name	Difficulty	Tags
CSES	Flight Discount	Easy	Show Tags SP
Gold	Milk Pumping	Easy	Show Tags SP
Gold	Why Did the Cow Cross the Road	Easy	Show Tags SP
Gold	Fine Dining	Easy	Show Tags SP
Gold	Shortcut	Normal	Show Tags SP
CSES	Investigation	Normal	Show Tags SP
Kattis	Robot Turtles	Normal	Show Tags SP
CSES	Flight Routes	Normal	Show Tags SP
IOI	2011 - Crocodile	Hard	Show Tags SP
JOI	2018 - Commuter Pass	Hard	Show Tags DP, SP
JOI	2021 - Robot	Hard	Show Tags SP
APIO	2011 - Find the Path	Hard	Show Tags Geometry, SP
Balkan OI	2012 - Shortest Paths	Hard	Show Tags SP
Balkan OI	2015 - Circus	Very Hard	Show Tags SP, Stack

Table of Contents

Shortest Paths with Non-Negative Edge Weights

Prerequisites

Table of Contents

Bellman-Ford

Floyd-Warshall

Tutorial

Optional: Incorrect Floyd-Warshall

Problem

Explanation

Implementation

Problems

Dijkstra

Tutorial

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

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

$\mathcal{O}(M\log N)$ Implementation

Problem

Implementation

Warning!

Optional: Faster Dijkstra

Problems

Module Progress:

Table of Contents

Shortest Paths with Non-Negative Edge Weights

Prerequisites

Table of Contents

Bellman-Ford

Floyd-Warshall

Tutorial

Optional: Incorrect Floyd-Warshall

Problem

Explanation

Implementation

Problems

Dijkstra

Tutorial

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

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

O(Mlog⁡N)\mathcal{O}(M\log N)O(MlogN) Implementation

Problem

Implementation

Warning!

Optional: Faster Dijkstra

Problems

Module Progress:Not Started

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

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

$\mathcal{O}(M\log N)$ Implementation

Module Progress: