플로이드-워셜 알고리즘은 그래프의 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과 달리 음수 가중치를 포함한 그래프에서도 작동합니다. 플로이드-워셜 알고리즘은 동적 프로그래밍 기법을 사용하여 모든 정점 사이의 최단 경로를 구합니다.

알고리즘 개념

플로이드-워셜 알고리즘은 3중 반복문을 사용하여 작동합니다. 각 반복은 ‘k’라는 중간 정점을 선택합니다. 즉, k를 거쳐가는 정점들을 확인하여 경로의 최단 길이를 업데이트합니다.

1. 그래프의 인접 행렬을 초기화합니다. 초기에는 직접적인 엣지의 가중치만 포함되며, 나머지 인접행렬의 값은 무한대로 설정됩니다.
2. 반복문을 통해 중간 정점 ‘k’를 선택합니다. (1부터 n까지)
3. 또 다른 반복문을 통해 출발 정점 ‘i’와 도착 정점 ‘j’를 선택합니다. (1부터 n까지)
4. 현재 경로의 길이와 ‘i’에서 ‘k’를 거쳐 ‘j’로 가는 경로의 길이를 비교하여 더 작은 값으로 경로를 업데이트합니다.
5. 모든 중간 정점에 대해 앞선 단계를 반복합니다.

위의 과정을 거치면, 모든 정점 쌍 사이의 최단 경로가 구해집니다.

파이썬으로 플로이드-워셜 알고리즘 구현

이제 파이썬에서 플로이드-워셜 알고리즘을 구현해보겠습니다. 아래는 그래프의 인접 행렬을 사용하여 플로이드-워셜 알고리즘을 구현한 예시 코드입니다.

def floyd_warshall(graph):
    n = len(graph)
    
    # 인접 행렬을 복사하여 초기화
    dist = [row[:] for row in graph]
    
    # 중간 정점을 선택하여 최단 경로 찾기
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# 인접 행렬 예시
inf = float('inf')
graph = [
    [0, inf, inf, 3],
    [2, 0, inf, inf],
    [inf, 7, 0, 1],
    [6, inf, inf, 0]
]

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

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

위의 코드는 다음과 같은 그래프를 사용하여 플로이드-워셜 알고리즘을 실행합니다.

      3
  +-------->
  |         \
  |          v
0 |   2    1
  | ^      |
  | \      v
  +-- 7 ---+
6

위의 코드는 예시 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾고 그 결과를 출력합니다. 결과는 다음과 같습니다.

[0, 10, 8, 3]
[2, 0, 9, 4]
[7, 7, 0, 1]
[6, 16, 14, 0]

위의 결과에서 (i, j) 위치의 값은 정점 i에서 정점 j로 가는 최단 경로의 길이를 나타냅니다.

플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 경로를 구할 수 있기 때문에 다양한 응용 분야에서 사용될 수 있습니다. 예를 들어 노드 간의 통신 비용을 찾는 네트워크 라우팅 문제, 최단 경로를 찾는 게임 알고리즘 등에 활용될 수 있습니다.