# 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.

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.

`> 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.

`> 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.