Bellman-Ford

Finds the shortest distance from a start vertex to every other vertex, even with negative weights, and reports a negative cycle when the start can reach one.

Time complexity O(V·E), gograph function path.BellmanFord.

How it works

Bellman-Ford starts like Dijkstra, with 0 at the start and infinity everywhere else, but it doesn't take vertices in order of distance. It goes through every edge, and when an edge gives its end a shorter distance, it lowers that distance. It repeats this pass one time fewer than there are vertices. A shortest path that doesn't repeat a vertex has at most that many edges, so after the last pass every distance is final.

Then it makes one more pass. If an edge can still shorten a distance, the start can reach a cycle whose weights add up to less than zero. Such a graph has no shortest path, since each trip around the cycle makes the path shorter, and path.BellmanFord returns ErrNegativeWeightCycle. It needs a directed, weighted graph and costs O(V·E).

Use it when some weights are negative, such as refunds, rewards or the negative logarithms of exchange rates, where a negative cycle is a chance for arbitrage. When no weight is negative, Dijkstra gives the same distances faster.

School run

Six places on the morning drive to school. Most streets go both ways, and each edge is the travel time in minutes.

A directed, weighted graph with 6 vertices and 13 edges.

How many minutes is the quickest drive from home to each place, including the school?

From Home, the shortest distances are 3 to Bridge, 4 to Bakery, 5 to Park, 9 to Library and 11 to School.

Step by step

Every distance starts at ∞, except Home, which is 0. Bellman-Ford checks all 13 edges in each of 5 passes, one fewer than the 6 vertices, then once more to look for a negative cycle.
Pass 1. Home to Bakery: 0 + 4 = 4, so Bakery's distance becomes 4.
Pass 1. Home to Bridge: 0 + 3 = 3, so Bridge's distance becomes 3.
Pass 1. Bakery to Park: 4 + 3 = 7, so Park's distance becomes 7.
Pass 1. Bridge to Park: 3 + 2 = 5, shorter than 7, so Park's distance becomes 5.
Pass 1. Park to Library: 5 + 4 = 9, so Library's distance becomes 9.

7 more steps lead to the last one:

Extra pass. No edge gives a shorter distance, so there is no negative cycle. Every distance from Home is final.

Use it in Go

dist, err := path.BellmanFord(g, "Home")
if err != nil {
	return err // path.ErrNegativeWeightCycle
}
fmt.Println(dist["School"])

Example graphs

School run, 6 vertices and 13 edges
Major currencies, 6 vertices and 20 edges
Delivery area, 8 vertices and 12 edges
Arbitrage loop, 8 vertices and 24 edges
One-way city, 45 vertices and 88 edges