Warshall算法-计算有向图的传递闭包

理解
代码

# -*- coding: utf-8 -*-
"""
Created on Fri May  6 14:22:51 2022

Warshall算法:
    用途:计算有向图的传递闭包
    复杂度:时间复杂度O(n^3)
    算法核心:
        如果A[i][j]为0,就将A[i][k]和A[k][i]进行与运算,并将其作为A[i][j]
"""
import numpy as np

def And(a,b):  #进行与运算
    if a==1 and b==1:
        return 1
    else:
        return 0

def Warshall(A,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if A[i][j]==0:
                    A[i][j]=And(A[i][k],A[k][j])                  
        print("第{}次".format(k+1))
        print(A)

A=np.array([[0,1,0,0],
            [0,0,1,0],
            [0,0,0,1],
            [0,0,0,0]])
Warshall(A, 4)

结果

第1次
[[0 1 0 0]
 [0 0 1 0]
 [0 0 0 1]
 [0 0 0 0]]
第2次
[[0 1 1 0]
 [0 0 1 0]
 [0 0 0 1]
 [0 0 0 0]]
第3次
[[0 1 1 1]
 [0 0 1 1]
 [0 0 0 1]
 [0 0 0 0]]
第4次
[[0 1 1 1]
 [0 0 1 1]
 [0 0 0 1]
 [0 0 0 0]]