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.

Time complexity O(V³), gograph function path.FloydWarshall.

Major currencies

Six major currencies and the rates a dealer quotes between them. Each edge is a trade, and its weight is minus the natural log of the exchange rate, so the shortest path is the best rate. Dollars buy more francs through EUR than directly. The rates are illustrative and close to market rates, and every loop of trades loses a little to the spread.

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

What is the best rate between every pair of currencies, trading through other currencies when that pays more?

Use it in Go

dist, err := path.FloydWarshall(g)
if err != nil {
	return err
}
fmt.Println(dist["CAD"]["GBP"])
fmt.Println(dist["GBP"]["CAD"]) // +Inf when there is no path

Example graphs

• Major currencies, 6 vertices and 20 edges
• Delivery area, 8 vertices and 12 edges
• Downtown grid, 20 vertices and 60 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.
• 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.

All algorithms