Floyd-Warshall Simple Example (Python)

Floyd-Warshall Example Code¶

The example graph used here comes from this video:

https://www.youtube.com/watch?v=4OQeCuLYj-4

In [1]:

V = 4
INF = 1e12

dist = [[0  , INF,  -2, INF],
        [  4,   0,   3, INF],
        [INF, INF,   0,   2],
        [INF,  -1, INF,   0]]

In [2]:

print("\nInitial distance matrix for the directed graph")
for row in dist:
    print(row)

Directed Graph Distance Matrix
[0, 1000000000000.0, -2, 1000000000000.0]
[4, 0, 3, 1000000000000.0]
[1000000000000.0, 1000000000000.0, 0, 2]
[1000000000000.0, -1, 1000000000000.0, 0]

In [3]:

# Floyd Warshall Algorithm 
for k in range(V): 
    for i in range(V): 
        for j in range(V): 
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

In [4]:

print("\nFinal distance matrix showing shortest distance between all pairs of nodes")
for row in dist:
    print(row)

Distance Matrix showing shortest distances between all pairs of nodes
[0, -1, -2, 0]
[4, 0, 2, 4]
[5, 1, 0, 2]
[3, -1, 1, 0]