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.

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 between every pair of stops, so a route can start anywhere, not just at the depot?

Use it in Go

dist, err := path.FloydWarshall(g)
if err != nil {
	return err
}
fmt.Println(dist["Depot"]["Station"])
fmt.Println(dist["Station"]["Depot"]) // +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