Shortest Paths with Negative Edge Weights

Bellman-Ford

Shortest Paths

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.

Implementation

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

Copy
#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++) {

Copy
import queue

n, m, q, s = map(int, input().split())
while True:
	if n == 0 and m == 0 and q == 0 and s == 0:
		break

	adj = [[] for _ in range(n)]
	for _ in range(m):
		u, v, w = map(int, input().split())

Finding Negative Cycles

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.

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Edge {
	int from, to;
	ll weight;
};

const int MAXN = 2505;

Copy
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}

Copy
INF = 10**18  # float('inf') will result in WA for some test cases


def bellman_ford(source: int):
	dist[source] = 0
	last_node_update = 0
	for i in range(1, n + 1):
		last_node_update = -1
		for (u, v, w) in graph:
			if dist[u] + w < dist[v]:

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

Problems

Timeline (USACO Camp):

• equivalent to Timeline (Gold) except $N,C\le 5000$ and negative values of $x$ are possible.

Floyd-Warshall

Implementation - APSP

Copy
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX_N = 150;
ll dist[MAX_N][MAX_N], bad[MAX_N][MAX_N];

int main() {
	int n, m, q;

Copy
INF = 10**18  # Note: using float('inf') results in TLE

n, m, q = map(int, input().split())
while True:
	if n == 0 and m == 0 and q == 0:
		break

	dist = [[INF] * n for _ in range(n)]
	bad = [[0] * n for _ in range(n)]

Problems

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.

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!