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.

Arbitrage loop

Eight currencies, where the quotes between GBP and JPY lag behind the others. Each edge is a trade, and its weight is minus the natural log of the exchange rate. Trading USD for GBP, GBP for JPY and JPY back to USD ends with about 0.2% more dollars than it started with, so that loop has a negative total weight. The rates are illustrative and close to market rates.

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

How much of each currency can a dollar buy at the best rate, and is there a loop of trades that ends with more dollars than it started with?

Use it in Go

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

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

More in Shortest paths

• Dijkstra: Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.
• Floyd-Warshall: Finds the shortest distance between every pair of vertices, even with negative weights, by letting paths stop at one more vertex in each round.

All algorithms