플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

다익스트라 알고리즘과의 차이점

다익스트라 : "한 지점"에서 다른 "모든 지점"까지의 최단경로
플로이드 워셜 : "모든 지점"에서 다른 "모든 지점"까지의 최단경로

플로이드 워셜 알고리즘

모든 노드에서 다른 모든 노드까지의 최단경로를 구하는 알고리즘
노드의 개수가 N개일 때, N개에 대해 N^2번의 연산을 하여 시간복잡도는 O(N^3) 이다.

모든 노드에 대하여 다른 모든 노드로 가는 최단거리 정보를 담아야 되기 때문에 2차원 리스트로 최단거리 테이블을 선언한다.
따라서 모든 노드에 대한 최단거리를 구하기 때문에 최단 거리가 가장 짧은 노드를 찾을 필요는 없다.

알고리즘 실행 과정

1. 그래프를 무한으로 초기화한다.
2. 자기 자신으로 가능 비용을 0 으로 초기화한다.
3. 입력값대로 a에서 b로 가는 비용을 초기화한다.
4. 3중 반복문을 돌려 a에서 b로 가는 비용을 직선 거리와 k를 거쳐가는 거리를 비교하여 최솟값으로 갱신한다.

플로이드 워셜 파이썬 코드

INF = int(1e9)

n, m = map(int, input().split())

graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신으로 가는 비용 : 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

# a에서 b로 가는 비용 : c
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            # a에서 b로 갈 때, k를 거쳐서 가는게 빠르면 갱신
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])


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