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.

One-way city

Forty-five intersections, I1 to I45, where I stands for intersection, numbered row by row from the top left with nine to a row. Most streets are one way, and the outer streets form a clockwise loop. Only the middle row (I19 to I27) and the middle column (I5, I14, I23, I32 and I41) go both ways, and each edge is the travel time in minutes.

A directed, weighted graph with 45 vertices and 88 edges.

How many minutes is the quickest drive between every pair of intersections, when one-way streets can make the way back longer than the way there?

Use it in Go

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