#3 최단거리 알고리즘 - Floyd-Warshall Algorithm

 Dijkstra's Algorithm이나 Bellman-Ford Algorithm이 한 정점에서 모든 정점으로의 최단거리를 구하는

알고리즘이라면 Floyd-Warshall Algorithm은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다. 

경유지점이 될 m, 시작점이 될 s, 도착점이 될 e를 각각 루프를돌며 dp[s][m] + dp[m][e] 로 최단거리를 갱신한다.

절차는 다음과 같다.

 

① 모든 정점간의 연결을 V * V 리스트 형태로 저장한다. (dp[i][i] == 0) 

② 먼저 경유점이 될 m을 고른 뒤(V) 시작점 s(V)와 끝점 e(V)도 각각 고른다  =>  O(V^3)  

③ dp[s][e]를 dp[s][m] + dp[m][e] 와 비교하여 갱신한다

④ 3중 반복문이 모두 돌고나면 dp[s][e] 는 s에서 e까지의 최단거리가 된다

 

구현이 굉장히 단순하지만 O(V^3)의 시간복잡도를 가지기에 정점의 수가 적을 때만 사용 가능한 방법이다.

특히 파이썬의 경우 작은 수의 V로도 시간초과가 나기 쉽상이니 주의할 필요가 있다.

 

알고리즘을 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
INF = float('inf')


def sol11404():
    n, m = int(input()), int(input())
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        dist[a - 1][b - 1] = min(dist[a-1][b-1], c)

    for k in range(n):
        for s in range(n):
            for e in range(n):
                dist[s][e] = min(dist[s][e], dist[s][k]+dist[k][e])
    print('\n'.join([' '.join(['0' if d == INF else str(d) for d in line]) for line in dist]))


if __name__ == '__main__':
    sol11404()

백준 온라인저지(Baekjoon Online Judge)의 11404번 문제(https://www.acmicpc.net/problem/11404)에 제출한 코드이다.