플로이드 와샬 (Floyd-Warshall) 알고리즘

플로이드 와샬 (Floyd-Warshall) 알고리즘

정의

플로이드 와샬 알고리즘은 모든 정점 간의 최단 경로를 찾는 알고리즘입니다. 가중치 그래프에서 사용될 수 있으며, 다이나믹 프로그래밍을 기반으로 합니다.

특징

1. 시간 복잡도: (O(V^3)) (여기서 (V)는 정점의 수)
2. 공간 복잡도: (O(V^2))
3. 음수 가중치: 음의 가중치를 가진 간선도 처리할 수 있습니다. 그러나 음수 사이클이 있는 경우에는 적용할 수 없습니다.
4. 모든 쌍의 최단 경로: 다익스트라 알고리즘과 달리 모든 정점에서 모든 정점까지의 최단 경로를 한 번에 구합니다.

사용 예

1. 도로 네트워크: 도시 간 최단 거리나 최소 비용을 구할 때
2. 통신 네트워크: 데이터 패킷이 최적의 경로로 전달되도록 할 때
3. 게임 경로 찾기: 게임 내에서 최단 경로를 찾을 때

C와 Python 비교

C 코드 예시

#define INF 99999
#define V 4

void floydWarshall(int graph[][V]) {
    int dist[V][V], i, j, k;
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    // 결과 출력 생략
}

Python 코드 예시

INF = 99999
V = 4

def floydWarshall(graph):
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    # 결과 출력 생략

비교

1. 타입 체크: C는 컴파일 타임에 타입을 체크하고, Python은 런타임에 체크합니다.
2. 코드 길이: Python 코드가 일반적으로 더 짧고 간결합니다.
3. 성능: C가 일반적으로 더 빠른 실행 속도를 보입니다.
4. 라이브러리: Python은 다양한 라이브러리와 패키지가 있어 개발이 빠르고 편리합니다.

두 언어 모두 플로이드 와샬 알고리즘을 구현하는 데 충분히 적합하며, 어떤 언어를 사용할지는 개발 환경, 성능 요구사항, 그리고 개발 팀의 노하우에 따라 결정될 수 있습니다.