🚌 플로이드-워셜(Floyd-Warshall) 알고리즘: 모든 정점 쌍 최단 경로 찾기

📚 플로이드-워셜 알고리즘이란?

플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프에서 가능한 모든 정점(노드) 쌍에 대한 최단 경로를 한 번에 찾아내는 알고리즘이다.

하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 다익스트라 알고리즘과는 달리, 플로이드-워셜은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구한다. 이 알고리즘의 가장 큰 특징 중 하나는 음수 가중치 간선이 포함된 그래프에서도 사용할 수 있다는 점이다. (단, 음수 가중치의 합이 0보다 작은 ‘음수 사이클’은 없어야 했다.)

이 알고리즘은 동적 계획법(Dynamic Programming) 에 기반을 두고 있으며, 로버트 플로이드와 스티븐 워셜에 의해 널리 알려졌다.

그 중, 플로이드 씨는 튜링상:trophy: 까지 받으셧다고…

💡 주요 개념

  • 모든 쌍 최단 경로 (All-Pairs Shortest Path): 그래프의 모든 정점 쌍 (u, v)에 대한 최단 경로를 찾는 문제다.
  • 동적 계획법 (Dynamic Programming): 큰 문제를 작은 하위 문제로 나누어 풀고, 하위 문제의 해를 저장하여 중복 계산을 피하는 방식이다. 플로이드-워셜은 ‘k’라는 중간 정점을 거쳐가는 경우를 순차적으로 고려하며 최단 경로를 갱신해 나간다.
  • 인접 행렬 (Adjacency Matrix): 그래프의 연결 관계를 2차원 배열로 나타낸 것이다. graph[i][j]는 정점 i에서 j로 가는 간선의 가중치를 의미한다. 직접 연결되지 않았다면 무한대(∞)로 표시한다.

🚀 플로이드-워셜 알고리즘 동작 방식 (단계별 설명)

플로이드-워셜 알고리즘은 간단한 3중 반복문 구조를 통해 모든 쌍의 최단 경로를 계산한다. 핵심 아이디어는 “i에서 j로 가는 최단 경로는, 중간에 k를 거쳐 가는 경로와 기존 경로 중 더 짧은 것이다” 이다.

  1. 초기화 (Initialization):
    • 최단 거리를 저장할 2차원 배열 dist[i][j]를 준비한다.
    • dist[i][j]를 두 정점 i, j를 잇는 간선의 가중치로 초기화한다. 만약 간선이 없다면 무한대(∞)로 설정한다.
    • 자기 자신으로 가는 경로 dist[i][i]는 0으로 설정한다.
  2. 경로 갱신 (Update Paths):
    • 그래프의 모든 정점 k에 대해, k를 중간 경유지로 사용하는 경우를 고려한다.
    • 모든 정점 쌍 (i, j)에 대해 다음을 비교하고 갱신한다.
      • 기존 최단 경로: dist[i][j]
      • k를 거쳐 가는 경로: dist[i][k] + dist[k][j]
    • 만약 k를 거쳐 가는 경로가 더 짧다면, dist[i][j] 값을 dist[i][k] + dist[k][j]로 갱신한다. 
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  3. 반복 (Repeat):
    • 모든 정점 k에 대해 2번 단계를 반복하면, dist 배열에는 모든 정점 쌍 간의 최단 경로가 저장된다.

가장 중요한 점은 3중 반복문에서 중간 경유지인 k에 대한 반복문이 가장 바깥쪽에 위치해야 한다는 점이다.

k번 정점까지를 경유지로 고려했을 때의 최단 경로가 다음 계산에 올바르게 사용되어야 하기 때문!

⚠️ 중요한 특징 및 시간 복잡도

  • 시간 복잡도: O(V^3) (V는 정점의 수). 3중 반복문 구조 때문에 정점의 개수가 많아지면 실행 시간이 급격히 늘어날 수 있다.
  • 음수 가중치 처리: 음수 가중치를 가진 간선이 있어도 잘 동작하지만, 합이 음수인 사이클(음수 사이클)이 존재하면 최단 경로를 찾을 수 없다. (계속 순환하면 비용이 무한히 작아지기 때문이다.)
  • 구현의 간결함: 알고리즘의 로직이 3중 반복문으로 매우 간단하여 구현하기 쉽다.
  • 동적 계획법 기반: ‘k-1’까지의 정점을 경유지로 고려한 최단 경로 정보를 바탕으로 ‘k’를 경유지로 포함하는 최단 경로를 계산해 나간다.

💻 파이썬 구현 예시

다음은 플로이드-워셜 알고리즘을 파이썬으로 구현한 예시다. 입력 graph는 인접 행렬 형태로 주어졌다고 가정했다.

def floyd_warshall(graph):
    """
    플로이드-워셜 알고리즘을 사용하여 모든 정점 쌍 간의 최단 거리를 계산한다.

    Args:
        graph (list of lists): 그래프를 인접 행렬 형태로 표현한 2차원 리스트.
                               연결되지 않은 경우 float('inf') 값을 가짐.

    Returns:
        list of lists: 모든 정점 쌍 간의 최단 거리가 저장된 2차원 리스트.
    """
    # 정점의 개수
    num_vertices = len(graph)
    
    # 최단 거리 테이블을 그래프 자체로 초기화 (깊은 복사)
    dist = [row[:] for row in graph]

    # k: 경유하는 노드
    for k in range(num_vertices):
        # i: 출발 노드
        for i in range(num_vertices):
            # j: 도착 노드
            for j in range(num_vertices):
                # i에서 j로 가는 기존 경로보다 k를 거쳐가는 경로가 더 짧은 경우 갱신
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# --- 예시 그래프 정의 (인접 행렬) ---
# 무한대(infinity) 값 정의
INF = float('inf')

# graph[i][j]는 i에서 j로 가는 가중치를 의미
# 자기 자신으로 가는 비용은 0
graph = [
    [0, 5, INF, 10],
    [INF, 0, 3, INF],
    [INF, INF, 0, 1],
    [INF, INF, INF, 0]
]

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

# --- 결과 출력 ---
print("모든 정점 쌍 간의 최단 경로:")
for row in shortest_paths:
    print(row)

# 출력 결과:
# [0, 5, 8, 9]
# [inf, 0, 3, 4]
# [inf, inf, 0, 1]
# [inf, inf, inf, 0]

✅ 마무리

플로이드-워셜 알고리즘은 모든 정점 사이의 최단 경로를 구해야 할 때 매우 유용한 알고리즘이었다.
비록 시간 복잡도는 높지만, 코드가 간결하고 음수 가중치도 처리할 수 있다는 장점이 있다.
그래프의 크기가 작고 모든 쌍의 최단 경로 정보가 필요할 때 강력한 성능을 발휘한다.