플로이드-워셜 알고리즘

 그래프의 최단경로를 구할 수 있는 알고리즘이다. 특히 '모든 노드에 대해서 최단거리를 구하고 싶을 때 사용'한다. (반면, 다익스트라 알고리즘은 특정 노드 하나의 최단거리를 구하는 것에 특화되어 있다). 기본적으로 주어진 그래프에 대해서 다음과 같은 점화식을 수행한다.

 

DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]) 

 

 즉 주어진 그래프에 대해서 특정 원소를 지나서 도달할 수 있는 경우의 수들을 차례로 고려하며 업데이트하는 것이다. 이때 i, j, k에 대해서 모두 노드의 개수만큼 순회해야하기 때문에 플로이드-워셜 알고리즘의 시간복잡도는 (O(N^3))이다. 따라서 노드의 개수가 1000개만 되어도 사용할 수 없다. 정리해보자면 다음과 같다. 

---

장점: 구현이 매우 간단하다.

 단점: 시간 복잡도가 O(N^3)이다.

---

예시 

입력

input1 = '''4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2'''

 

INF = int(1e9)

n, m = list(map(int, input1.split()[:2]))
array = [tuple(map(int, row.split())) for row in input1.split('\n')[2:]]

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

# 자기 자신 거리는 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# graph initialize
for i in range(m):
    a, b, c = array[i]
    graph[a][b] = c
    
# ===================점화식 적용===================
for k in range(1, n + 1):
    for a in range(1, n + 1):
        if a == k:
            continue
        for b in range(1, n + 1):
            if b == k:
                continue
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# =================================================
            
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print('inf', end=' ')
        else:
            print(graph[a][b], end=' ')
    print()