플로이드 워셜(Floyd-Warshall) 알고리즘 - 파이썬(python)

플로이드 워셜 알고리즘

-모든 정점에서 다른 모든 정점으로 가는 최소비용을 구하는 알고리즘

양방향 그래프

위 그래프를 2차원 배열의 형태로 보면

arr=[

      [0,5,INF,8],

      [7,0,9,INF],

      [2,INF,0,4],

      [INF,INF,3,0],

]

플로이드 워셜 코드

def floyd_warshall():
    dist=[[INF]* num for i in range(num)]
    
    for i in range(num):
        for j in range(num):
            dist[i][j]=arr[i][j]
    
    # 거처가는 노드
    for k in range(num):
        # 출발 노드
        for i in range(num):
            # 도착 노드
            for j in range(num):
                if dist[i][k]+dist[k][j]<dist[i][j]:
                    dist[i][j]=dist[i][k]+dist[k][j]
    
    return dist
         

INF=10000000
num=4
arr=[
      [0,5,INF,8],
      [7,0,9,INF],
      [2,INF,0,4],
      [INF,INF,3,0],
]

dist=floyd_warshall()

for i in range(num):
    for j in range(num):
        print(dist[i][j],end=' ')
    print()

결과

 

 

참고 : https://blog.naver.com/ndb796/221234427842