Graph-Algorithms-Python/Floyd_Warshall.py at main · ArevikKH/Graph-Algorithms-Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
n = 4
m =[
    [0, 4, 1, 100],
    [100, 0, 6, 100],
    [4, 1, 0, 2],
    [100, 100, 100, 0]
]

def floydWarshall(m):
    dp = m
    next_ = [[None] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if m[i][j] != 100:
                next_[i][j] = j

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
                    next_[i][j] = next_[i][k]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    dp[i][j] = -100
                    next_[i][j] = -1

    return dp

print(floydWarshall(m))