# 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

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

cp-algo | ||||

cp-algo | with Bellman-Ford | |||

CP2 |

### 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 $V-1$ edges, where $V$ stands for the number of vertices in the graph. Because of that, the algorithm iterates through at most all edges $V-1$ times. Hence, it runs in $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 $N$th 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 $x_1,x_2,\ldots,x_N$ with constraints in the form $x_i-x_j\ge c$, compute a feasible solution.

#### Resources

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

MIT | Linear Programming Trick |

#### Problems

Timeline (USACO Camp):

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

RMI | Normal |

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

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

APIO | Hard | ## 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.

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

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