PrevNext
Has Not Appeared
 0/6

Shortest Paths with Negative Edge Weights

Authors: Benjamin Qi, Andi Qu, Dong Liu, F. Bruno D. R.

Returning to Bellman-Ford and Floyd-Warshall.

Bellman-Ford

Shortest Paths

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

Solution

Although this is a Single Source Shortest Paths problem, we can not use the known Dijkstra's algorithm, because we have negative weights on edges. An alternative is to use the Bellman-Ford algorithm. The algorithm first considers all the paths which use 1 edge. Then it calculates all the paths with at most 2 edges, and so on. If the graph has no negative cycle, then the shortest path between the source and any other vertice should have at most V1V-1 edges, where VV stands for the number of vertices in the graph. Because of that, the algorithm iterates through at most all edges V1V-1 times. Hence, it runs in O(EV)O(E \cdot V).

If the graph has a negative cycle, we can detect a vertice in this cycle by running another relaxation. In this problem, belonging to a negative cycle means the distance to that point is negative infinity. Notice that all points that are reachable from those will also have minus infinity cost. In the solution below, we detect all the negative cycles and save the point from which we detected the cycle. We then do a BFS with those points as sources.

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, q, s;
cin >> n >> m >> q >> s;
while (!(n == 0 && m == 0 && q == 0 && s == 0)) {
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; i++) {

Finding Negative Cycles

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

Solution

As mentioned in cp-algorithms, we relax the edges N times. If we perform an update on the NNth iteration, there is an negative cycle.

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
int from, to;
ll weight;
};
const int MAXN = 2505;

Java

import java.io.*;
import java.util.*;
public class CyclesFinding {
static final int MAX_N = 2500;
static int[] parent = new int[MAX_N + 1];
static long[] dist = new long[MAX_N + 1];
static List<Edge> graph = new ArrayList<>();
// CodeSnip{Edge}

Simple Linear Programming

You can also use shortest path algorithms to solve the following problem (a very simple linear program).

Given variables x1,x2,,xNx_1,x_2,\ldots,x_N with constraints in the form xixjcx_i-x_j\ge c, compute a feasible solution.

Resources

Resources
MIT

Linear Programming Trick

Problems

Timeline (USACO Camp):

  • equivalent to Timeline (Gold) except N,C5000N,C\le 5000 and negative values of xx are possible.
StatusSourceProblem NameDifficultyTags
RMINormal

Floyd-Warshall

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

Solution - APSP

C++

const int MOD = 1000000007;
const ll INF = 1e18;
int n, m, q;
ll dist[150][150], bad[150][150];
void solve() {
F0R(i, n) F0R(j, n) dist[i][j] = INF, bad[i][j] = 0;
F0R(i, n) dist[i][i] = 0;
F0R(i, m) {

Problems

StatusSourceProblem NameDifficultyTags
APIOHard
Show TagsAPSP, Binary Search

Modified Dijkstra

The Dijkstra code presented earlier will still give correct results if there are no negative cycles. However, the same running time bound no longer applies, as demonstrated by subtasks 1-6 of the following problem.

StatusSourceProblem NameDifficultyTags
APIOHard
Show TagsOutput Only, SP

This problem forces you to analyze the inner workings of the three shortest-path algorithms we presented here. It also teaches you about how problemsetters could create hack cases!

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!

PrevNext