플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 그래프 이론에서 모든 꼭짓점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 동적 계획법을 기반으로 하며, 로버트 플로이드와 스티븐 워셜에 의해 1962년에 고안되었다.

주요 용도는 가중 방향 그래프에서 모든 정점 쌍 사이의 최단 거리와 경로를 계산하는 것이다. 다른 최단 경로 알고리즘과 달리, 이 알고리즘은 음의 가중치를 가진 간선이 존재하는 그래프도 처리할 수 있다는 특징이 있다. 단, 그래프에 음의 사이클이 존재하지 않아야 한다.

이 알고리즘은 컴퓨터 과학의 여러 분야, 특히 네트워크 분석과 경로 탐색 문제에 널리 활용된다. 알고리즘의 결과는 모든 정점 쌍에 대한 최단 거리 정보를 담은 행렬 형태로 도출되며, 추가적인 자료 구조를 통해 실제 최단 경로를 추적하는 것도 가능하다.

플로이드-워셜 알고리즘은 동적 계획법을 기반으로 하여 그래프 상의 모든 꼭짓점 쌍 사이의 최단 거리를 구하는 방법이다. 이 알고리즘의 핵심 아이디어는 '중간 경유점'의 개념을 점진적으로 확장해 나가는 것이다. 구체적으로, 각 단계 k에서 '1번부터 k번까지의 꼭짓점만을 중간 경유점으로 사용할 때'의 모든 쌍 최단 거리를 계산하고 이를 다음 단계의 기초로 삼는다.

알고리즘은 일반적으로 2차원 배열을 사용하여 거리 정보를 저장하며, 초기 상태에서는 직접 연결된 간선의 가중치로 배열을 채운다. 이후, 모든 꼭짓점 k에 대해, 모든 꼭짓점 쌍 (i, j)를 검사하며, 'i에서 k를 거쳐 j로 가는 경로'가 기존의 'i에서 j로 가는 직접 경로'보다 짧은지 확인한다. 만약 더 짧다면 거리 값을 더 짧은 값으로 갱신한다. 이 과정을 모든 k에 대해 반복하면, 결국 모든 꼭짓점을 경유점으로 고려한 상태의 최단 거리 행렬이 완성된다.

이 방식은 벨만-포드 알고리즘이나 다익스트라 알고리즘과 달리, 한 번의 실행으로 모든 출발점에 대한 결과를 도출할 수 있다는 장점이 있다. 또한, 알고리즘의 구조 상 음의 가중치를 가진 간선이 존재해도 올바르게 동작한다는 특징이 있다. 다만, 음의 사이클이 그래프 내에 존재하는 경우에는 최단 거리가 정의되지 않으며, 알고리즘을 통해 이 사이클의 존재를 감지할 수 있다.

플로이드-워셜 알고리즘의 원리는 비교적 직관적이면서도 강력하여, 네트워크 분석, 경로 탐색, 지리 정보 시스템 등 다양한 분야의 모든 쌍 최단 경로 문제 해결에 널리 활용되고 있다.

플로이드-워셜 알고리즘의 의사 코드는 알고리즘의 핵심적인 동작 방식을 간결하게 보여준다. 이 알고리즘은 동적 계획법을 기반으로 하여, 3중 반복문을 통해 모든 노드 쌍 사이의 최단 거리를 점진적으로 갱신한다.

알고리즘의 입력은 일반적으로 인접 행렬 형태의 그래프이다. 이 행렬은 초기에 노드 i에서 노드 j로의 직접 연결 거리로 초기화되며, 직접 연결이 없는 경우 무한대의 값으로 설정된다. 또한 각 노드에서 자기 자신으로의 거리는 0으로 설정된다. 알고리즘의 핵심은 중간 경유지 노드 k를 하나씩 고려하면서, i에서 j로 가는 기존 경로보다 k를 경유하는 새로운 경로가 더 짧은지 확인하고, 더 짧다면 거리 값을 갱신하는 것이다.

의사 코드는 다음과 같은 구조를 가진다.

이 과정이 완료되면 거리 행렬 D는 모든 노드 쌍 사이의 최단 거리를 담게 된다. 경로 자체를 추적해야 하는 경우, 각 거리 갱신 시에 어느 노드를 통해 왔는지 기록하는 별도의 행렬을 함께 유지하며 갱신한다. 이 의사 코드 구조는 그래프의 노드 수가 N일 때, 시간 복잡도가 O(N^3)이 됨을 명확히 보여준다.

플로이드-워셜 알고리즘의 시간 복잡도는 O(V^3)이다. 여기서 V는 그래프의 정점(Vertex)의 수를 의미한다. 이는 알고리즘의 핵심 연산이 모든 정점 쌍 (i, j)에 대해, 모든 정점 k를 중간 경유지로 고려하는 삼중 반복문 구조로 이루어져 있기 때문이다.

구체적으로 알고리즘은 V x V 크기의 거리 행렬을 초기화한 후, 각 정점 k를 경유지로 설정하고, 모든 i와 j 쌍에 대해 dist[i][j]와 dist[i][k] + dist[k][j] 값을 비교하여 더 작은 값으로 갱신하는 과정을 반복한다. 이 세 단계의 반복이 모두 정점 수 V에 비례하므로, 전체 연산 횟수는 V * V * V, 즉 V^3에 비례하게 된다.

이러한 시간 복잡도는 다익스트라 알고리즘을 모든 정점에 대해 한 번씩 적용하는 것과 동일하지만, 플로이드-워셜 알고리즘은 구현이 간단하고 음의 가중치를 가진 간선이 있는 그래프에서도 안정적으로 동작한다는 장점이 있다. 그러나 정점의 수가 매우 많아지면 V^3의 계산량은 실용적이지 않을 수 있어, 대규모 그래프에는 모든 쌍 최단 경로 문제를 위한 다른 알고리즘이나 분산 컴퓨팅 기법이 고려되기도 한다.

플로이드-워셜 알고리즘의 공간 복잡도는 주로 최단 경로 거리를 저장하는 데 사용되는 2차원 배열의 크기에 의해 결정된다. 기본 구현에서는 그래프의 정점 수를 V라고 할 때, V x V 크기의 2차원 배열을 사용하여 모든 정점 쌍 사이의 최단 거리 정보를 저장한다. 따라서 필요한 공간은 V의 제곱에 비례하며, 이를 빅 오 표기법으로 표현하면 O(V^2)이다.

이 공간 복잡도는 알고리즘의 핵심인 동적 계획법 테이블을 유지하는 데 필수적이다. 각 단계 k에서 정점 i에서 j로 가는 최단 경로가 정점 k를 경유하는지 여부를 확인하고 갱신하기 위해서는 모든 쌍의 거리 정보가 동시에 접근 가능해야 하기 때문이다. 만약 경로 자체를 재구성해야 하는 경우, 각 정점 쌍에 대해 직전에 방문한 정점을 저장하는 추가적인 2차원 배열이 필요해 공간 복잡도는 여전히 O(V^2)를 유지한다.

일부 최적화를 통해 공간 사용량을 줄일 수 있는 방법도 존재하지만, 일반적으로 플로이드-워셜 알고리즘은 모든 쌍 최단 경로 문제를 해결하는 대가로 비교적 높은 공간을 요구한다고 평가받는다. 이는 다익스트라 알고리즘과 같은 단일 출발점 알고리즘을 각 정점에 대해 반복 적용하는 방식과 대비되는 특징이다.

플로이드-워셜 알고리즘은 동적 계획법을 기반으로 하여 그래프 상의 모든 정점 쌍 간의 최단 거리를 구하는 대표적인 최단 경로 문제 해결 방법이다. 이 알고리즘의 가장 큰 특징은 다익스트라 알고리즘이나 벨만-포드 알고리즘과 달리 단일 출발점이 아닌 모든 쌍에 대한 최단 경로를 한 번에 계산한다는 점이다.

이 알고리즘은 음의 가중치를 가진 간선이 존재하는 그래프에서도 정상적으로 동작한다는 장점이 있다. 또한, 알고리즘의 핵심 연산인 삼중 반복문을 통해 각 단계마다 특정 정점을 경유하는 경우를 고려하여 최단 거리 테이블을 갱신하는 방식으로 동작한다. 이 과정에서 음의 사이클이 존재하는지 여부도 자체적으로 감지할 수 있다.

구현 측면에서 볼 때, 플로이드-워셜 알고리즘은 코드가 매우 간결하고 직관적이라는 특징을 가진다. 기본 구조는 거리 정보를 저장하는 2차원 배열을 사용한 삼중 반복문으로 이루어져 있어 이해하고 구현하기가 비교적 쉽다. 이로 인해 교육 현장이나 알고리즘 문제 해결에서 널리 활용된다.

그러나 모든 정점 쌍에 대한 정보를 계산해야 하므로, 정점의 수가 V일 때 시간 복잡도와 공간 복잡도가 모두 O(V^3)과 O(V^2)로 나타난다. 이는 그래프의 크기가 커질수록 성능에 큰 부담이 될 수 있어, 밀집 그래프가 아니거나 특정 출발점에 대한 경로만 필요할 경우에는 다른 알고리즘을 선택하는 것이 더 효율적일 수 있다.

플로이드-워셜 알고리즘은 모든 꼭짓점 쌍 간의 최단 경로를 계산해야 하는 다양한 실제 문제에 널리 활용된다. 이 알고리즘의 핵심 강점은 음의 가중치 간선을 처리할 수 있다는 점과, 동적 계획법을 통해 모든 쌍의 거리를 한 번에 계산하는 데 있다.

주요 활용 분야는 다음과 같다.

또한, 알고리즘의 결과로 생성된 거리 행렬은 더 큰 시스템의 일부로 사용되기도 한다. 예를 들어, 교통 시뮬레이션이나 위치 기반 서비스의 백엔드 계산 모듈에 통합되어 실시간으로 최적 경로를 제공하는 기반 데이터를 만드는 데 쓰인다. 경로 추적 기능을 추가하면 실제로 어떤 정점들을 거쳐 가는지까지 재구성할 수 있어, 네비게이션 시스템에서 구체적인 이동 경로를 안내하는 데에도 응용 가능하다.

플로이드-워셜 알고리즘은 모든 꼭짓점 쌍에 대한 최단 거리를 보장하지만, 몇 가지 명확한 단점을 가지고 있다. 가장 큰 단점은 시간 복잡도와 공간 복잡도가 모두 높다는 점이다. 모든 꼭짓점 쌍을 고려하는 방식 때문에 시간 복잡도가 O(V^3)에 달해, 꼭짓점 수가 많은 대규모 그래프에서는 실행 시간이 매우 길어질 수 있다. 이는 다익스트라 알고리즘을 모든 꼭짓점에 대해 적용하는 것보다 비효율적일 수 있다. 또한 모든 쌍의 거리 정보를 저장해야 하므로 공간 복잡도도 O(V^2)로, 메모리 사용량이 꼭짓점 수의 제곱에 비례하여 증가한다.

알고리즘의 구조상 특정 유형의 문제에는 적합하지 않다. 예를 들어, 단일 출발점 최단 경로 문제를 해결할 때는 플로이드-워셜 알고리즘을 사용하는 것이 과도한 계산을 수행하는 것이 된다. 또한 그래프에 음의 가중치 순환이 존재하는 경우, 알고리즘은 최단 경로를 정확히 찾지 못하며 이를 감지할 수는 있지만 경로 자체는 올바르게 계산하지 않는다. 이는 벨만-포드 알고리즘과 같은 다른 알고리즘과 비교되는 부분이다.

실제 구현과 활용 측면에서도 고려할 점이 있다. 알고리즘의 코드는 간결하지만, 3중 반복문을 사용하는 구조는 상대적으로 병렬 처리나 최적화가 어려울 수 있다. 또한 경로 자체를 추적하기 위해서는 별도의 경로 복원 행렬을 추가로 유지해야 하는 부담이 있다. 따라서 매우 큰 그래프나 실시간 응용이 필요한 시스템에서는 이러한 복잡도 제약이 주요한 걸림돌이 된다.

플로이드-워셜 알고리즘은 모든 쌍 최단 경로 문제를 해결하는 대표적인 알고리즘이다. 이와 유사한 문제를 해결하거나 부분적으로 기능을 공유하는 다른 알고리즘들도 존재한다.

대표적인 비교 대상은 다익스트라 알고리즘이다. 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 단일 출발 최단 경로 알고리즘이다. 플로이드-워셜 알고리즘이 모든 정점 쌍에 대한 답을 구하는 반면, 다익스트라 알고리즘은 각 정점을 출발점으로 반복 실행해야 동일한 결과를 얻을 수 있다. 다만 다익스트라 알고리즘은 우선순위 큐를 사용할 경우 시간 복잡도가 더 낮은 경우가 많지만, 음의 가중치를 가진 간선을 처리하지 못한다는 제약이 있다.

음의 가중치가 포함된 그래프에서 단일 출발 최단 경로 문제를 해결하는 알고리즘으로는 벨만-포드 알고리즘이 있다. 이 알고리즘 또한 모든 정점 쌍에 대한 해를 구하려면 각 정점에 대해 반복 수행해야 한다. 플로이드-워셜 알고리즘은 구조적으로 벨만-포드 알고리즘과 유사한 점이 있으며, 특히 동적 계획법을 사용한다는 공통점이 있다.

더욱 제한된 조건이나 특수한 그래프에서 더 높은 성능을 보이는 알고리즘들도 연구되어 왔다. 예를 들어, 존슨의 알고리즘은 희소 그래프에서 모든 쌍 최단 경로를 계산할 때 플로이드-워셜 알고리즘보다 효율적일 수 있다. 이 알고리즘은 다익스트라 알고리즘과 벨만-포드 알고리즘을 결합하여 사용한다.

플로이드-워셜 알고리즘은 개발자인 로버트 플로이드와 스티븐 워셜의 이름을 따서 명명되었다. 이 알고리즘은 1962년에 처음 소개되었으며, 동적 계획법을 활용한 대표적인 최단 경로 알고리즘으로 자리 잡았다. 알고리즘의 핵심 아이디어는 모든 중간 정점을 거치는 경우를 고려하여 점진적으로 최단 거리를 갱신하는 것이다.

이 알고리즘은 종종 다익스트라 알고리즘이나 벨만-포드 알고리즘과 비교된다. 다익스트라 알고리즘이 하나의 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 반면, 플로이드-워셜 알고리즘은 모든 정점 쌍에 대한 최단 거리를 한 번에 계산한다는 점이 근본적으로 다르다. 또한, 음의 가중치를 가진 간선이 있는 그래프에서도 올바르게 동작한다는 점이 벨만-포드 알고리즘과 유사한 특징이다.

플로이드-워셜 알고리즘은 그 구현이 매우 간결하고 직관적이라는 평가를 받는다. 세 개의 중첩된 반복문으로 구성된 기본 구조는 알고리즘의 원리를 이해하기 쉽게 만든다. 이러한 단순함과 강력함 덕분에 그래프 이론을 배우는 과정에서 필수적으로 다루어지며, 컴퓨터 과학 교육에서 중요한 위치를 차지하고 있다.