플로이드 워셜 알고리즘

: 모든 지점에서 다른 모든 지점까지의 최단 경로 모두 구하기

특징

• DP의 활용
• 시간 복잡도 : $O(N^3)$ → $N$번의 단계 마다 $O(N^2)$의 연산을 통해 현재 거쳐가는 모든 경로 고려

동작 원리

모든 노드에 대해 →$O(N)$
해당 노드를 거쳐가는 경우 고려하기 → $O(^{n-1} P_2)$ == $O(N^2)$

상태 정의

$D_{ab}$ : a에서 b로 가는 최소 비용

이라고 정의했을때, a→b 의 최소 비용은 a에서 b로 바로 가는 비용과 k를 거쳐서, 즉 a→k→b의 비용 중 작은 값이다. 점화식으로 표현하면,

$D_{ab} = min(D_{ab}, D_{ak}+D_{kb})$

Step 0 상태의 초기화

$D_{ab}$ : a에서 b로 가는 최소 비용에 따라 테이블을 초기화한다.

출발/도착	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	INF
3번	5	INF	0	4
4번	INF	INF	2	0

Step 1 i번 ~N번 노드를 거쳐가는 경우

• 1번 노드를 거쳐갈때,

  $^{n-1} P_2$가지의 경우의 수가 있다.

  : (2,3), (2,4), (3,2), (3,4), (4,2), (4,3)

  $D_{23} = min(D_{23}, D_{21}+D_{13})$과 같이 나머지 쌍에 대해서도 전부 계산하고, 값을 갱신한다.

2번~ 4번에 대해서도 마찬가지를로 처리해준다.

최종 결과

출발/도착	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

구현

INF = int(1e9)

n, m = map(int, input().split()) #노드 개수, 간선 개수
start = int(input()) #시작 노드
graph = [[INF]*(n+1) for _ in range(n+1)] #노드 연결 정보

#자기 자신->자기 자신
for i in range(1, n+1):
    graph[i][i] = 0

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):
            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()

출처

나동빈님의 이것이 취업을 위한 코딩테스트다