6-8. 그래프: 플로이드-워셜

1. 플로이드-워셜 알고리즘 소개

플로이드-워셜 알고리즘은 그래프 내의 모든 노드 쌍 간의 최단 경로를 효율적으로 계산하는 알고리즘입니다. 그래프 이론과 알고리즘 분야에서 널리 사용되며, 특히 다중 출발지-다중 도착지 최단 경로 문제를 해결하는 데 특화되어 있습니다. 이는 특정 노드에서 다른 모든 노드로의 최단 경로를 구하는 다익스트라(Dijkstra) 알고리즘이나 벨만-포드(Bellman-Ford) 알고리즘과는 달리, 그래프 내의 모든 노드 쌍 (u, v)에 대해 u에서 v로 가는 최단 경로를 한 번의 실행으로 모두 계산합니다.

1) 배경

최단 경로 문제는 그래프 이론의 핵심 문제 중 하나이며, 다양한 실생활 문제에 적용됩니다. 예를 들어, 지도 애플리케이션에서 두 지점 간의 최단 거리를 찾는 데 사용되거나, 네트워크 라우팅 프로토콜에서 최적의 경로를 결정하는 데 활용될 수 있습니다. 다익스트라 알고리즘과 벨만-포드 알고리즘은 단일 출발점에서 다른 모든 노드로의 최단 경로를 계산하는 데 효율적이지만, 모든 노드 쌍 간의 최단 경로를 구하려면 각 노드를 출발점으로 하여 알고리즘을 반복적으로 실행해야 합니다. 플로이드-워셜 알고리즘은 이러한 반복적인 계산을 피하고, 단일 알고리즘 실행으로 모든 쌍의 최단 경로를 계산하는 방법을 제공합니다.

2) 핵심 아이디어

플로이드-워셜 알고리즘은 동적 프로그래밍(Dynamic Programming) 방식을 기반으로 합니다. 이 알고리즘은 그래프의 각 노드를 중간 노드(intermediate node)로 고려하여, 두 노드 간의 최단 경로를 갱신해 나갑니다. 알고리즘은 그래프 내의 모든 노드를 순차적으로 중간 노드로 고려하며, 각 단계에서 모든 노드 쌍 간의 최단 경로를 업데이트합니다.

2. 알고리즘 원리

플로이드-워셜 알고리즘의 핵심은 다음과 같은 아이디어에 기반합니다.

1. 초기화: 각 노드 쌍 (u, v)에 대해, u에서 v로 가는 직접적인 경로의 가중치를 저장합니다. 만약 직접적인 경로가 없다면, 무한대(∞)로 초기화합니다. 각 노드 u에서 u로 가는 경로는 가중치가 0으로 초기화됩니다.

2. 반복: 각 노드 k를 중간 노드로 하여 모든 노드 쌍 (i, j)에 대해 최단 경로를 업데이트합니다. 즉, i에서 j로 가는 기존 경로와 i에서 k를 거쳐 j로 가는 경로를 비교하여 더 짧은 경로를 선택합니다.

   • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

   이 식에서 dist[i][j]는 노드 i에서 노드 j까지의 현재까지 계산된 최단 경로의 가중치를 나타냅니다.

1) 상세 과정

알고리즘은 세 개의 중첩된 루프로 구성됩니다.

• 가장 바깥쪽 루프 (k): 중간 노드를 선택합니다.
• 두 번째 루프 (i): 출발 노드를 선택합니다.
• 가장 안쪽 루프 (j): 도착 노드를 선택합니다.

각 k에 대해, 모든 노드 쌍 (i, j)에 대해 i에서 k를 거쳐 j로 가는 경로가 i에서 j로 가는 기존 경로보다 짧은지 확인하고, 그렇다면 최단 경로를 업데이트합니다.

2) 예시

간단한 그래프를 예로 들어 알고리즘의 동작을 시각적으로 설명해 보겠습니다.

위 그림은 4개의 노드와 가중치를 가진 유향 그래프를 나타냅니다. 플로이드-워셜 알고리즘은 이 그래프 내의 모든 노드 쌍 간의 최단 경로를 계산합니다.

1. 초기화: 초기 거리 행렬은 다음과 같습니다. 무한대(∞)는 연결되지 않은 경로를 나타냅니다.

   [[0, 5, ∞, 10], [∞, 0, 3, ∞], [∞, ∞, 0, 1], [∞, ∞, ∞, 0]]

2. k = 0 (노드 0을 중간 노드로 고려): 노드 0을 중간 노드로 사용하여 다른 모든 노드 쌍 간의 최단 경로를 갱신합니다. 이 경우, 0에서 0으로 가는 경로는 0, 0에서 1로 가는 경로는 5, 0에서 3으로 가는 경로는 10입니다. 0을 경유하는 경로는 없으므로 거리 행렬은 변하지 않습니다.

   [[0, 5, ∞, 10], [∞, 0, 3, ∞], [∞, ∞, 0, 1], [∞, ∞, ∞, 0]]

3. k = 1 (노드 1을 중간 노드로 고려): 노드 1을 중간 노드로 사용하여 경로를 갱신합니다. 예를 들어, 노드 2에서 노드 0으로 가는 경로가 있다면, 2 -> 1 -> 0으로 가는 경로를 고려합니다. 이 경우, 노드 2에서 노드 1로 가는 경로는 없으므로, 갱신이 일어나지 않습니다.

   [[0, 5, 8, 10], [∞, 0, 3, ∞], [∞, ∞, 0, 1], [∞, ∞, ∞, 0]]

4. k = 2 (노드 2를 중간 노드로 고려): 노드 2를 중간 노드로 사용하여 경로를 갱신합니다. 예를 들어, 노드 1에서 노드 3으로 가는 경로가 있다면, 1 -> 2 -> 3으로 가는 경로를 고려합니다. 이 경우, 노드 1에서 2를 거쳐 3으로 가는 경로 (3+1=4)는 기존 경로보다 짧습니다.

   [[0, 5, 8, 9], [∞, 0, 3, 4], [∞, ∞, 0, 1], [∞, ∞, ∞, 0]]

5. k = 3 (노드 3을 중간 노드로 고려): 노드 3을 중간 노드로 사용하여 경로를 갱신합니다. 노드 0에서 3을 거쳐 다른 노드로 가는 경로는 없으므로, 갱신이 일어나지 않습니다.

   [[0, 5, 8, 9], [∞, 0, 3, 4], [∞, ∞, 0, 1], [∞, ∞, ∞, 0]]

   알고리즘이 종료되면, 각 dist[i][j]는 노드 i에서 노드 j까지의 최단 경로의 가중치를 나타냅니다.

3. 구현

플로이드-워셜 알고리즘은 비교적 간단하게 구현할 수 있습니다. 다음은 파이썬으로 작성된 예제 코드입니다.

def floyd_warshall(graph):
    """
    플로이드-워셜 알고리즘 구현

    Args:
        graph: 인접 행렬로 표현된 그래프.
               graph[i][j]는 노드 i에서 노드 j로 가는 간선의 가중치.
               만약 간선이 없으면 무한대(float('inf'))로 설정.
               노드 i에서 노드 i로 가는 경로는 0으로 설정.

    Returns:
        모든 노드 쌍 간의 최단 경로를 담은 거리 행렬.
    """
    n = len(graph)
    dist = [([float('inf')] * n) for _ in range(n)]

    # 초기화
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            else:
                dist[i][j] = graph[i][j]

    # 플로이드-워셜 알고리즘
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

# 예시 그래프 (인접 행렬)
graph = [
    [0, 5, float('inf'), 10],
    [float('inf'), 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 1],
    [float('inf'), float('inf'), float('inf'), 0]
]

# 플로이드-워셜 실행
shortest_paths = floyd_warshall(graph)

# 결과 출력
for row in shortest_paths:
    print(row)

1) 코드 설명

• floyd_warshall(graph) 함수는 인접 행렬 graph를 입력으로 받습니다.
• 초기화 단계에서, 각 노드 쌍 간의 거리를 초기화합니다. 직접적인 경로가 존재하면 해당 가중치를 사용하고, 그렇지 않으면 무한대(float('inf'))를 사용합니다. 자기 자신으로 가는 경로는 0으로 설정합니다.
• 세 개의 중첩된 루프를 사용하여 모든 중간 노드 k에 대해 최단 경로를 업데이트합니다. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 구문을 통해 i에서 j로 직접 가는 경로와 i에서 k를 거쳐 j로 가는 경로를 비교하여 더 짧은 경로를 선택합니다.
• 결과적으로, shortest_paths 행렬은 모든 노드 쌍 간의 최단 경로 가중치를 담고 있습니다.

4. 응용 및 활용 사례

플로이드-워셜 알고리즘은 다양한 분야에서 활용될 수 있습니다.

1) 네트워크 라우팅

• 네트워크 라우팅 프로토콜: 라우터는 플로이드-워셜 알고리즘을 사용하여 네트워크 내의 모든 다른 라우터까지의 최단 경로를 계산하고, 이를 기반으로 트래픽을 효율적으로 전달합니다.

2) 지도 애플리케이션

• 경로 탐색: 지도 애플리케이션은 플로이드-워셜 알고리즘을 사용하여 지도상의 모든 지점 간의 최단 거리를 미리 계산하고 저장해 둡니다. 사용자가 목적지를 입력하면, 저장된 데이터를 기반으로 빠르게 최단 경로를 찾을 수 있습니다.

3) 사회 연결망 분석

• 소셜 네트워크 분석: 소셜 네트워크에서 두 사람 간의 최단 거리를 계산하여 연결 강도를 파악하거나, 중앙성(centrality) 지표를 계산하는 데 활용될 수 있습니다.

4) 게임 개발

• 게임 내 길 찾기: 게임 맵에서 NPC(Non-Player Character)나 플레이어가 이동할 수 있는 최단 경로를 계산하는 데 사용됩니다.

5. 주의사항 및 트러블슈팅

1) 음수 가중치 사이클

플로이드-워셜 알고리즘은 음수 가중치를 가진 간선이 있는 그래프에서도 사용할 수 있습니다. 그러나 음수 가중치 사이클이 존재할 경우, 알고리즘은 무한 루프에 빠질 수 있습니다. 즉, 경로의 가중치가 계속 감소하여 최단 경로가 정의되지 않습니다. 이러한 경우, 알고리즘을 실행하기 전에 음수 가중치 사이클의 존재 여부를 확인해야 합니다.

• 음수 가중치 사이클을 확인하기 위해, 알고리즘 실행 후 dist[i][i] 값이 음수인 노드가 있는지 확인합니다. 만약 있다면, 해당 노드는 음수 가중치 사이클에 포함되어 있음을 의미합니다.

2) 메모리 사용량

플로이드-워셜 알고리즘은 모든 노드 쌍 간의 최단 경로를 저장해야 하므로, 메모리 사용량이 O(V^2)입니다. 여기서 V는 노드의 수를 나타냅니다. 따라서, 노드의 수가 매우 큰 그래프에서는 메모리 사용량이 문제가 될 수 있습니다.

3) 시간 복잡도

플로이드-워셜 알고리즘의 시간 복잡도는 세 개의 중첩된 루프로 인해 O(V^3)입니다. 이는 다익스트라 알고리즘(힙 기반 구현 시 O(E log V))이나 벨만-포드 알고리즘(O(VE))보다 높을 수 있습니다. 여기서 E는 간선의 수입니다. 따라서, 그래프가 희소(sparse) 그래프인 경우에는 다른 알고리즘이 더 효율적일 수 있습니다. 그러나, 모든 노드 쌍 간의 최단 경로를 구해야 하는 경우에는 플로이드-워셜 알고리즘이 여전히 유용합니다.

6. 결론

플로이드-워셜 알고리즘은 그래프 내의 모든 노드 쌍 간의 최단 경로를 효율적으로 계산하는 강력한 도구입니다. 동적 프로그래밍을 기반으로 하며, 간단한 구현과 다양한 응용 분야를 가지고 있습니다. 음수 가중치 사이클의 존재 여부와 메모리/시간 복잡도를 고려하여 적절한 상황에서 활용하는 것이 중요합니다.