플로이드 워셜 알고리즘(파이썬)

플로이드 워셜 알고리즘이란?

그래프의 모든 노드 사이의 최단거리를 구하는 알고리즘이다.

다익스트라 알고리즘과의 비교

공통점:
다익스트라 알고리즘과 플로이드 워셜 알고리즘은 노드 사이의 최단거리를 구하는 것!

차이점:
다익스트라 알고리즘의 간선의 가중치는 항상 양수이어야 하고 두 노드 사이의 최단거리를 도출해내는 반면 플로이드 워셜 알고리즘의 간선의 가중치는 음수도 가능하고 모든 노드 사이의 최단거리를 한번에 계산합니다.

플로이드 워셜의 원리

위와같은 그래프가 있고 모든 노드 사이의 최단 거리를 알아내려고 합니다. 오른쪽 테이블은 최단거리 테이블 입니다.

• 테이블에서 나타나는 행은 출발노드 열은 도착노드입니다.
• 0: 자기 자신을 향하는 노드 즉 행과 열이 같은 경우는 0으로 초기화합니다.
• INF: 출발 노드와 끝 노드가 연결되어있지 않음을 의미합니다. INFINITY(무한대)로 표기
• 그 외 숫자: 간선의 가중치를 입력해 놓습니다.

• 위의 그래프에 표시된 것 처럼 노드 2를 경유한 경우 중 하나를 나타낸 것입니다.
• 1에서 3으로 이동하는 최단거리의 경우 노드 2를 경유하게 되면 노드 1에서 2로 경유한 거리 + 노드 2에서 3으로 경유한 거리(1 + 1 = 2) 총 2의 거리이고 원래의 최단거리 3 보다 더 작은 것을 확인할 수 있습니다.
• 결국 노드1에서 노드3으로 이동하는 최단거리 테이블은 2로 갱신됩니다.
• 이 경유하는 과정을 모든 노드에도 적용시켜줍니다.

아래 최단거리 테이블이 변화하는 과정을 살펴보겠습니다!

첫번째로 1을 경유했을 경우 갱신되는 테이블입니다.

두번째로 2를 경유했을 경우 갱신되는 테이블입니다.

이런 방식으로 모든 노드를 경유하면서 갱신했을 때 비로소 최단거리 테이블이 완성이 되는 것입니다.

코드

import sys
input = sys.stdin.readline

# 노드의 수
n = int(input().strip())
# 간선의 개수
m = int(input().strip())
INF = int(1e9)
# 최단거리 테이블 생성
distance = [[INF] * (n + 1) for _ in range(n + 1)]
# 출발노드 도착노드 거리 정보 입력받기
# 무방향 그래프이므로 반대의 경우에도 한번 더 dist값을 삽입해준다.
for _ in range(m):
    start, end, dist = map(int, input().strip().split())
    distance[start][end] = dist
    distance[end][start] = dist

# 자기 자신으로 가는 거리 0으로 초기화
for i in range(1, n + 1):
    distance[i][i] = 0

# 플로이드 워셜 알고리즘
def floyd():
	# i: 경유하는 노드, k: 출발노드, h: 도착노드
    for i in range(1, n + 1):
        for k in range(1, n + 1):
            for h in range(1, n + 1):
                distance[k][h] = min(distance[k][i] + distance[i][h], distance[k][h])


floyd()
for i in range(1, n + 1):
    for k in range(1, n + 1):
        if distance[i][k] == INF:
            print("INF", end=' ')
        else:
            print(distance[i][k], end=' ')
    print()

후기

플로이드 워셜 알고리즘 구현은 상당히 짧았다. 하지만 그냥 언뜻 봐서는 이해되었다고 착각하고 있었던 것이었다! 이렇게 그래프를 그려보고 도식화해보니 어떻게 플로이드 워셜 알고리즘이 작동하는지 더 자세히 알 수 있었다!