Przejdź do treści

Floyd-Warshall

🔗 Opis problemu

Implementacja

 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
import math
from typing import List
from pprint import pprint

def floyd_warshall(graph: List[List[int]]):
    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                if i == j or k == i or k == j:
                    continue

                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

f = math.inf
graph = [
    [0, 5, f, f, f, f, 5],
    [5, 0, 3, 3, f, f, 5],
    [f, 3, 0, 1, f, f, f],
    [f, 3, 1, 0, 5, 4, 3],
    [f, f, f, 5, 0, 2, f],
    [f, f, f, 4, 2, 0, 5],
    [5, 5, f, 3, f, 5, 0],
]

floyd_warshall(graph)

pprint(graph)