[알고리즘] 최단 경로 - 플로이드 워셜 알고리즘

woo0_hooo·6일 전
0

python

목록 보기
23/24

플로이드 워셜 알고리즘

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

특징

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

출처

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

profile
Hongik CE

0개의 댓글