# Shortest Paths with Non-Negative Edge Weights

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

Bellman-Ford, Floyd-Warshall, and 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

### Tutorial

Resources | ||||
---|---|---|---|---|

CPH | example calculation, code | |||

cp-algo | code, why it works | |||

PAPS | code, why it works | |||

CP2 |

### Optional: Incorrect Floyd-Warshall

From this 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

Focus Problem – try your best to solve 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++

#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;constexpr long long BIG = 1e18; // We can't use LLONG_MAX because of overflowint main() {

Java

import java.io.*;import java.util.*;public class ShortestRoutesII {// We can't use Long.MAX_VALUE because of overflowprivate static final long BIG = (long)1e18;public static void main(String[] args) {Kattio io = new Kattio();

Python

### Warning!

Due to Python's bad constant factor, this code TLEs on a couple of test cases.

# 1e18 is used instead of float('inf') for performance reasonsBIG = int(1e18)n, m, q = map(int, input().split())min_dist = [[BIG] * n for _ in range(n)]for _ in range(m):a, b, c = map(int, input().split())a, b = a - 1, b - 1

### Problems

This algorithm is used as the first step of the following:

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Gold | Hard | ## Show TagsAPSP, DP |

## Dijkstra

### Tutorial

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

Resources | ||||
---|---|---|---|---|

cp-algo |

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

Resources | ||||
---|---|---|---|---|

CPH | code | |||

cp-algo | ||||

CPC | ||||

CP2 | ||||

alexyd88 |

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

Resources | ||||
---|---|---|---|---|

Benq |

### Problem

Focus Problem – try your best to solve this problem before continuing!

### Implementation

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

Here's an animation of how the algorithm works:

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.

#include <bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;// Adjacency list of (neighbour, edge weight)vector<vector<pair<int, int>>> neighbors(n);for (int i = 0; i < m; i++) {

Java

import java.io.*;import java.util.*;public class ShortestRoutesI {Code Snippet: Pair Class (Click to expand)public static void main(String[] args) {Kattio io = new Kattio();int n = io.nextInt();

Python

import heapqn, m = map(int, input().split())# Adjacency list of (neighbour, edge weight)graph = [[] for _ in range(n)]for i in range(m):a, b, c = map(int, input().split())graph[a - 1].append((b - 1, c))

### 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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsSP | |||

Gold | Easy | ## Show TagsSP | |||

Gold | Easy | ## Show TagsSP | |||

Gold | Easy | ## Show TagsSP | |||

Gold | Normal | ## Show TagsSP | |||

CF | Normal | ## Show TagsBinary Search, Coordinate Compression, DP, SP | |||

CSES | Normal | ## Show TagsSP | |||

Kattis | Normal | ## Show TagsSP | |||

CSES | Normal | ## Show TagsSP | |||

AC | Hard | ## Show TagsGreedy, SP | |||

IOI | Hard | ## Show TagsSP | |||

JOI | Hard | ## Show TagsDP, SP | |||

JOI | Hard | ## Show TagsSP | |||

APIO | Hard | ## Show TagsGeometry, SP | |||

Balkan OI | Hard | ## Show TagsSP | |||

Balkan OI | Very Hard | ## Show TagsSP, Stack |

### 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!