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.

Delivery area

Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.

A directed, weighted graph with 8 vertices and 12 edges.

How many minutes is the quickest drive from the depot to each stop?

From Depot, the shortest distances are 2 to Market, 3 to Bakery, 8 to School, 10 to Park, 11 to Library, 12 to Clinic and 14 to Station.

Step by step

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

14 more steps lead to the last one:

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

Use it in Go

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

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