Algorithm - [ 최단 경로 (2) ]

date

Jul 12, 2023

slug

algorithm-07

author

status

Public

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’ 에 사용할 수 있는 알고리즘이다.

(다익스트라 알고리즘은 ‘한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘이다.)

플로이드 워셜 알고리즘의 특징

플로이드 워셜 알고리즘은 2차원 리스트에 ‘최단 거리’ 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.

플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다. 노드의 개수가 N 이라고 할 때, N 번 만큼의 단계를 반복하면 ‘점화식에 맞게’ 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍으로 볼 수 있다.

구체적인 (K 번의 단계에 대한) 점화식은 다음과 같다. 점화식이 의미는 ‘a 에서 b 로가는 최소 비용’과 ‘a 에서 k 를 거쳐 b 로 가는 비용’을 비교하여 더 작은 값으로 갱신한다는 것이다.

따라서 전체적으로 3중 반복문을 이용하여 이 점화식에 따라 최단 거리 테이블을 갱신하면 된다.

플로이드 워셜 알고리즘 소스코드


# 플로이드 워셜 알고리즘
# 무한 설정
INF = int(1e9)

# 노드, 간선 수
n, m = map(int, input().split())

# 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

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A 에서 B 로 가는 거리는 C 라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(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('INFINITY', end=' ')
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=' ')
    print()

플로이드 워셜 알고리즘을 수행하는 단계에서, 1번 노드부터 마지막 노드까지 거쳐 갈 때가 더 빠른 경우가 존재한다면 빠른 경우로 최단 거리를 갱신한다.

예를 들어 다음과 같은 그래프가 있을 때,

아래와 같이 초기 테이블을 설정할 수 있다.

이때 플로이드 워셜 알고리즘을 수행하는 단계에서, 첫 반복문을 통해(1번 노드를 거치는 경우) 1번 노드에서 3번 노드를 가는 경우는 INF 인 상태 그대로이므로 갱신이 안 되지만, 두 번째 반복을 통해 2번 노드를 거치게 되는 경우가 되면 4 (1번에서 2번으로) + 7 (2번 노드에서 3번으로) = 11이 되어 갱신된다.

플로이드 워셜 알고리즘의 시간 복잡도

플로이드 워셜 알고리즘은 단계마다 ‘거쳐 가는 노드’를 기준으로 알고리즘을 수행한다.

하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. 현재 확인하고 있는 노드를 제외하고, N - 1 개의 노드 중에서 서로 다른 노드 (a, b) 쌍을 선택한다.

이후에 a → 현재 노드 → b 로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다. 다시 말해 개의 쌍을 단계마다 반복해서 확인하면 된다.

이때 는 이라고 볼 수 있기 때문에, 노드의 개수가 N 개 일 때 모든 경로를 고려하기 위해 N 번의 단계를 수행하면 전체 시간 복잡도는 이라고 할 수 있다.

(출처: 이것이 코딩 테스트다)