Bellman-Ford and Floyd-Warshall
Handle negative edge weights and detect negative cycles with Bellman-Ford, and compute the shortest distance between every pair of vertices with Floyd-Warshall.
When are weights negative?
Bellman-Ford
string[] names = { "S", "A", "B", "C", "D" };var edges = new List<(int From, int To, int W)>{ (3, 4, 2), (1, 4, 5), (1, 3, -4), (2, 3, 4), (2, 1, 3), (0, 2, 2), (0, 1, 6)}; var dist = BellmanFord(names.Length, edges, 0);Console.WriteLine(dist is null ? "Negative cycle!" : string.Join(" ", names.Zip(dist, (n, d) => $"{n}:{d}"))); edges.Add((4, 1, -6)); // D → A: closes the loop A → C → D → A (−8)dist = BellmanFord(names.Length, edges, 0);Console.WriteLine(dist is null ? "Negative cycle!" : string.Join(" ", names.Zip(dist, (n, d) => $"{n}:{d}"))); static long[]? BellmanFord(int n, List<(int From, int To, int W)> edges, int source){ var d = new long[n]; Array.Fill(d, long.MaxValue); d[source] = 0; for (int pass = 1; pass < n; pass++) // V − 1 passes { bool changed = false; foreach (var (u, v, w) in edges) if (d[u] != long.MaxValue && d[u] + w < d[v]) { d[v] = d[u] + w; changed = true; } if (!changed) return d; // nothing moved: done early } foreach (var (u, v, w) in edges) // one extra pass if (d[u] != long.MaxValue && d[u] + w < d[v]) return null; // still improving: negative cycle return d;}S:0 A:5 B:2 C:1 D:3 Negative cycle!
!= long.MaxValue check: “∞ + a negative weight” must stay ∞, not wrap around to a huge negative number.
Floyd-Warshall: every pair at once
d[i, j] is the shortest route from i to j that only stops at vertices 0…k. The update is one line: is going via k better?
const int INF = int.MaxValue / 2; // half, so INF + INF does not overflowint n = 4;var d = new int[n, n];for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i, j] = i == j ? 0 : INF; foreach (var (a, b, w) in new[] { (0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2), (2, 0, 5), (2, 3, 1), (3, 0, 2) }) d[a, b] = w; for (int k = 0; k < n; k++) // allow k as a stopover for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (d[i, k] + d[k, j] < d[i, j]) d[i, j] = d[i, k] + d[k, j]; for (int i = 0; i < n; i++){ var row = new List<string>(); for (int j = 0; j < n; j++) row.Add(d[i, j] >= INF ? "∞" : d[i, j].ToString()); Console.WriteLine(string.Join("\t", row));}0 3 5 6 5 0 2 3 3 6 0 1 2 5 7 0
d[i, i] < 0) reveals a negative cycle.
| Algorithm | Question | Negative weights | Time |
|---|---|---|---|
Show a hint
Show the solution
const int INF = int.MaxValue / 2;string names = "ABCDEFG";int n = names.Length;var d = new int[n, n];for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i, j] = i == j ? 0 : INF; var roads = new[] { ("AB", 4), ("AD", 2), ("BE", 3), ("BC", 6), ("DE", 5), ("CE", 2), ("CF", 3), ("EG", 4), ("DG", 7), ("FG", 1), ("EF", 6) };foreach (var (r, w) in roads){ int a = names.IndexOf(r[0]), b = names.IndexOf(r[1]); d[a, b] = d[b, a] = w;} for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (d[i, k] + d[k, j] < d[i, j]) d[i, j] = d[i, k] + d[k, j]; int bestPlace = 0, bestWorst = INF;for (int i = 0; i < n; i++){ int worst = 0; for (int j = 0; j < n; j++) worst = Math.Max(worst, d[i, j]); if (worst < bestWorst) { bestWorst = worst; bestPlace = i; }}Console.WriteLine($"{names[bestPlace]}: every place within {bestWorst} minutes");E: every place within 7 minutes
Remember
Bellman-Ford relaxes every edge V − 1 times: O(V · E), works with negative weights. If an extra pass still improves something, there is a negative cycle. Floyd-Warshall computes all pairs with three loops (k outermost): O(V³). Pick the algorithm by question (one source / all pairs) and weights (unweighted / non-negative / negative).