플로이드-와샬 알고리즘은 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘을 개선하여 사용하며, 음의 가중치를 가진 그래프에서도 동작합니다.

알고리즘 원리

플로이드-와샬 알고리즘은 다음과 같은 원리로 동작합니다:

1. 그래프의 인접 행렬을 초기화합니다. 만약 경로가 존재하지 않은 경우, 해당 위치의 값을 무한대로 설정합니다.
2. 모든 정점들을 순회하며, 각 정점을 중간 지점으로 고려하여 최소 경로를 갱신합니다. 이때, 현재 정점을 경유해서 가는 경로가 더 짧은 경우에만 최소 경로를 갱신합니다.
3. 중간 지점을 한 번씩 바꿔가며 모든 정점을 순회하여 최소 경로를 찾습니다.

이러한 과정을 모든 정점에 대해 반복하면, 모든 정점 쌍 사이의 최단 경로를 찾을 수 있습니다.

코드 예제

아래는 플로이드-와샬 알고리즘을 파이썬으로 구현한 예제입니다:

def floyd_warshall(graph):
    dist = graph.copy()

    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

위의 코드는 인접 행렬 형태의 그래프를 입력으로 받아, 각 정점 쌍 사이의 최단 경로를 계산하여 반환하는 함수입니다.

시간 복잡도

플로이드-와샬 알고리즘의 시간 복잡도는 O(V^3)입니다. 여기서 V는 그래프의 정점의 수를 뜻합니다.

요약

플로이드-와샬 알고리즘은 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘으로, 다익스트라 알고리즘을 개선하여 음의 가중치를 가진 그래프에서도 동작합니다. 이 알고리즘은 인접 행렬 형태의 그래프를 입력으로 받아 최단 경로를 계산합니다.