cp_library/alg/graph/floyd_warshall_check_neg_cycle_fn.py

View this file on GitHub
Last update: 2025-03-30 20:17:47+09:00

Depends on

Verified with

test/aoj/grl/grl_1_c_floyd_warshall.test.py

Code

import cp_library.alg.graph.__header__

def floyd_warshall(G, N, directed=True):
    if directed:
        from cp_library.alg.graph.floyd_warshall_directed_fn import floyd_warshall
    else:
        from cp_library.alg.graph.floyd_warshall_fn import floyd_warshall
    D = floyd_warshall(G, N)
    return any(D[i][i] < 0 for i in range(N)), D

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def floyd_warshall(G, N, directed=True):
    if directed:
        from math import inf
        
        def floyd_warshall(G, N) -> list[list[int]]:
            D = [[inf]*N for _ in range(N)]
        
            for u, edges in enumerate(G):
                D[u][u] = 0
                for v,w in edges:
                    D[u][v] = min(D[u][v], w)
            
            for k, Dk in enumerate(D):
                for Di in D:
                    if Di[k] == inf: continue
                    for j in range(N):
                        if Dk[j] == inf: continue
                        Di[j] = min(Di[j], Di[k]+Dk[j])
            return D
    else:
        
        def floyd_warshall(G, N) -> list[list[int]]:
            D = [[inf]*N for _ in range(N)]
        
            for u, edges in enumerate(G):
                D[u][u] = 0
                for v,w in edges:
                    D[u][v] = min(D[u][v], w)
            
            for k, Dk in enumerate(D):
                for i, Di in enumerate(D):
                    if Di[k] == inf: continue
                    for j in range(i):
                        if Dk[j] == inf: continue
                        Di[j] = D[j][i] = min(Di[j], Di[k]+Dk[j])
            return D
    D = floyd_warshall(G, N)
    return any(D[i][i] < 0 for i in range(N)), D