[Python] 플로이드 와샬 (Floyd Warshall)

플로이드 와샬 (Floyd Warshall)

개념

• 플로이드 와샬 알고리즘은 모든 노드에서 모든 노드로의 최단 경로를 구하는 알고리즘이다.
• 거쳐가는 노드를 기준으로 알고리즘을 수행한다는 특징이 있다.
• 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드 간 최소의 비용을 계산한다.

VS 다익스트라 알고리즘

• 다익스트라 알고리즘은 하나의 노드에서 출발했을 때 다른 모든 노드로의 최단 경로를 구하는 알고리즘이다.
• 가장 적은 비용을 하나씩 선택을 해서 그 적은 비용을 가지는 노드의 인접한 노드들로 가는 비용을 하나씩 계산하는 방식

예시

위의 그래프를 이차원 배열로 만들면 아래와 같다.
테이블이 의미하는 바는 현재까지 계산된 최소 비용 이다.
이차원 배열을 반복적으로 갱신하여 최종적으로 모든 최소 비용을 구해야 한다.

1. 노드 1을 거쳐가는 경우 (= 노드 1을 중간노드로 설정한 경우 / ? -> 1 -> ?)

노드 N을 거쳐가는 경우 (= 노드 N을 중간노드로 설정한 경우 / ? -> N -> ?)

최종 결과

코드

백준 : 11404 플로이드

## 플로이드
import sys
from math import inf
input=sys.stdin.readline

n=int(input())
m=int(input())
res=[[inf]*n for _ in range(n)]


def floydWarshall():
    for i in range(m):
        a, b, c = map(int, input().split())
        if res[a-1][b-1]>c:
            res[a-1][b-1] = c
        #res[a-1][b-1] = min(res[a-1][b-1], c)

    for k in range(n): #k = 거쳐가는 노드
        res[k][k]=0 #자기 자신의 노드는 0으로 처리
        for i in range(n): #i = 출발 노드
            for j in range(n): #j = 도착 노드
                # res[i][j]=min(res[i][j], res[i][k]+res[k][j])
                if res[i][k]+res[k][j] < res[i][j]:
                    res[i][j] = res[i][k] + res[k][j]

    for i in range(n):
        for j in range(n):
            if res[i][j]==inf:
                res[i][j]=0
            print(res[i][j], end=' ')
        print()

floydWarshall()