플로이드 워셜 알고리즘 (Floyd-Warshall) 개념 및 예시코드

모든 지점에서 모든 지점까지의 최단 경로를 구하는 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 모든 노드 쌍 간의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘이 단일 시작점에서 출발하여 다른 모든 노드로의 최단 경로를 구하는 반면, 플로이드 워셜 알고리즘은 모든 노드 쌍에 대해 최단 경로를 구할 수 있다는 점에서 차이가 있다.

이 알고리즘은 다이나믹 프로그래밍을 활용하며, 단계마다 특정 노드를 중간 노드로 거쳐가는 경우를 고려하여 경로를 갱신한다. 이 과정에서 2차원 리스트를 이용해 모든 경로의 최단 거리를 저장한다.

시간복잡도는 (O(N^3))이며, 노드의 개수가 많아질수록 처리 시간이 급격히 증가하는 특징이 있다.

---

플로이드 워셜 알고리즘 동작 방식

알고리즘은 크게 다음과 같은 단계로 이루어진다.

1. 그래프 초기화
   모든 노드 간의 초기 거리를 설정한다. 초기에는 자기 자신으로 가는 거리는 0으로 설정하고, 직접 연결되지 않은 노드 간의 거리는 무한대로 설정한다.
2. 간선 정보 입력
   입력받은 간선 정보를 바탕으로, 해당 간선이 연결된 두 노드 간의 거리를 입력받은 값으로 갱신한다.
3. 중간 노드 고려
   각 노드를 중간 노드로 설정하고, 이 노드를 거쳐 가는 경로가 기존 경로보다 짧은 경우 경로를 갱신한다.
4. 결과 출력
   최종적으로 모든 노드 쌍 간의 최단 경로를 출력한다. 만약 두 노드가 연결되어 있지 않다면 무한대(INFINITY)로 출력한다.

---

코드 구현

아래는 플로이드 워셜 알고리즘을 Python으로 구현한 코드이다.

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드 개수 및 간선 개수 입력받기
n = int(input())
m = int(input())

# 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(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):
        # 도달할 수 없는 경우 INFINITY 출력
        if graph[a][b] == INF:
            print("INFINITY", end=' ')
        # 도달할 수 있는 경우 거리 출력
        else:
            print(graph[a][b], end=' ')
    print()

---

코드 설명

1. INF = int(1e9)
   무한대 값을 설정한다. 이는 두 노드가 서로 연결되어 있지 않은 경우를 표현하기 위함이다.
2. graph = [[INF] * (n + 1) for _ in range(n + 1)]
   ( (n+1) \times (n+1) ) 크기의 2차원 리스트를 생성하고, 모든 값을 무한대로 초기화한다.
3. 자기 자신으로 가는 비용을 0으로 설정한다.이는 자기 자신으로 가는 경로의 비용이 항상 0이기 때문이다.
4. for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0
5. 간선 정보를 입력받아 초기화한다.각 간선에 대해 노드 (a)에서 노드 (b)로 가는 비용을 (c)로 설정한다.
6. for _ in range(m): a, b, c = map(int, input().split()) graph[a][b] = c
7. 플로이드 워셜 알고리즘을 수행한다.이중 반복문을 통해 모든 노드 쌍에 대해 중간 노드 (k)를 거치는 경우와 직접 연결된 경우 중 더 짧은 거리를 선택하여 갱신한다.
8. 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])
9. 결과를 출력한다.각 노드 쌍에 대해 최단 거리를 출력한다. 연결되지 않은 경우에는 "INFINITY"로 표시한다.
10. 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()

---

예제 입력 및 출력

입력 예시

4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

출력 예시

0 4 8 6 
3 0 7 9 
5 9 0 4 
7 11 2 0

---

정리

플로이드 워셜 알고리즘은 모든 노드 쌍에 대한 최단 경로를 구하는 효율적인 방법이다. 다만 시간복잡도가 (O(N^3))이기 때문에 노드의 개수가 많아질 경우 다익스트라 알고리즘과 같은 다른 방법을 고려하는 것이 좋다. 이러한 특성 때문에 플로이드 워셜 알고리즘은 노드 개수가 비교적 적을 때 사용하는 것이 바람직하다.

따라서 플로이드 워셜 알고리즘은 교통망 분석, 네트워크 플로우와 같이 모든 지점 간의 경로를 구해야 하는 문제에서 유용하게 사용된다.