Day 65: Floyd-Warshall

Floyd’s algorithm is another method to find the shortest path in graph.

I have already implemented Dijkstra’s algorithm about two weeks ago. However, Dijkstra doesn’t work on graphs with negative weights on edges.

Remember, we had a set of shortest paths found so far and any path extension would lead to a longer path. It is pretty easy to find a counter-example and break the algorithm if you have negative weights.

Floyd’s algorithm works even with negative weights. In advance, it is able to detect if there is a negative cycle in the graph. Note that graph with negative cycle containing vertices U, V has no shortest path between U, V.

black edge has weight=1, red edge has weight=-1

Which one is the shortest path between (0, 1)?
length(0, 1) = -1
length(0, 1, 2, 0, 1) = -2
length(0, 1, 2, 0, 1, 2, 0, 1) = -3


The idea of the algorithm is to iteratively build shortest paths between some vertices U and V using only limited set of vertices. When this set is extended by another vertex W, we can either get a shorter path through W or we have already had the best one.

shortest(U, V) = min( shortest(U, V), shortest(U, W) + shortest(W, V) )

You can see that the relationship is recursive. Iterative construction used in the algorithm is yet another showcase of dynamic programming technique.

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

algorithm

def floyd(graph):
# initialize matrix
distance = nx.adjacency_matrix(graph).todense().astype(float)
distance[distance == 0] = np.inf
np.fill_diagonal(distance, 0)

# find shortest paths
for k, i, j in product(range(len(graph)), repeat=3):
distance[i, j] = min(distance[i, j],
distance[i, k] + distance[k, j])

# negative cycle detection
if i == j and distance[i, j] < 0:
return k, i, 'negative cycle detected'
    # shortest paths
return {
(i, j): distance[i, j]
for i, j in product(range(len(graph)), repeat=2)
if i != j and not np.isinf(distance[i, j])
}

graph

Directed graph; black edges have weight=1, red edges have weight=-1.

zero-cost path (1, 0, 2, 3, 4)
> graph = generate_graph(5, edge_prob=.4, pos_weight_prob=.7)
> floyd(graph)
{(0, 1): 0.0, (0, 2): -1.0, (0, 3): -2.0, (0, 4): -1.0,
(1, 0): 1.0, (1, 2): 0.0, (1, 3): -1.0, (1, 4): 0.0,
(2, 0): 2.0, (2, 1): 1.0, (2, 3): -1.0, (2, 4): 0.0,
(3, 4): 1.0}

graph with negative cycle

Directed graph; black edges have weight=1, red edges have weight=-1.

negative cycle (4, 1, 0, 4)
> graph = generate_graph(5, edge_prob=.4, pos_weight_prob=.6)
> floyd(graph)
(1, 4, 'negative cycle detected')
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.