단일 출발점 최단 경로 문제

다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 탐욕 알고리즘으로, 단일 출발점 최단 경로 문제를 해결하는 가장 널리 알려진 방법이다. 이 알고리즘은 모든 간선의 가중치가 음수가 아닐 때 정확한 최단 경로를 보장한다. 기본 아이디어는 시작 정점에서 가장 가까운 정점부터 순차적으로 최단 거리를 확정해 나가는 것이다. 알고리즘은 아직 방문하지 않은 정점들 중 시작점으로부터 현재까지 알려진 거리가 가장 짧은 정점을 선택하고, 이 정점을 경유하여 이웃 정점들까지의 거리를 갱신하는 과정을 반복한다.

구현은 일반적으로 우선순위 큐 자료구조를 사용하여 효율성을 높인다. 초기에는 시작 정점의 거리를 0으로, 다른 모든 정점의 거리를 무한대로 설정한다. 우선순위 큐에는 (거리, 정점) 쌍이 저장되며, 큐에서 가장 짧은 거리를 가진 정점을 꺼내어 처리한다. 해당 정점의 각 인접 정점에 대해, 현재 저장된 거리보다 선택된 정점을 경유하는 새로운 경로의 거리가 더 짧다면 거리 정보를 갱신하고 우선순위 큐에 다시 넣는다. 이 과정은 우선순위 큐가 빌 때까지, 즉 모든 정점의 최단 거리가 확정될 때까지 계속된다.

다익스트라 알고리즘의 시간 복잡도는 사용하는 자료구조에 따라 달라진다. 이진 힙을 기반으로 한 우선순위 큐를 사용할 경우 시간 복잡도는 O((V+E) log V)이다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다. 이는 그래프의 크기가 커질수록 효율적인 성능을 보여준다. 그러나 알고리즘의 가장 큰 제약은 간선의 가중치에 음의 가중치가 존재하는 경우에는 올바른 결과를 도출하지 못한다는 점이다. 음의 가중치를 다루기 위해서는 벨만-포드 알고리즘과 같은 다른 알고리즘이 필요하다.

이 알고리즘은 네트워크 라우팅 프로토콜이나 지리 정보 시스템의 경로 탐색, 교통 시스템 모델링 등 실생활의 다양한 최단 경로 탐색 문제에 광범위하게 응용된다. 특히 OSPF와 같은 링크 상태 라우팅 프로토콜의 핵심 알고리즘으로 사용된다.

벨만-포드 알고리즘은 가중 그래프에서 단일 출발점 최단 경로 문제를 해결하는 또 다른 대표적인 알고리즘이다. 이 알고리즘은 다익스트라 알고리즘과 달리 음의 가중치를 가진 간선이 존재하는 그래프에서도 사용할 수 있다는 점이 가장 큰 특징이다. 또한, 음의 사이클이 존재하는 경우 이를 감지하여 최단 경로가 존재하지 않음을 알려줄 수 있다.

알고리즘의 기본 동작 원리는 동적 계획법에 기반한다. 시작 정점에서 다른 모든 정점까지의 최단 거리 추정값을 초기화한 후, 모든 간선에 대해 완화 연산을 반복적으로 수행한다. 이 완화 과정은 정점의 개수를 V라고 할 때, V-1번 반복하여 최단 경로를 찾아낸다. 만약 V-1번의 반복 이후에도 거리 추정값이 갱신된다면, 이는 그래프에 음의 사이클이 존재한다는 증거가 된다.

벨만-포드 알고리즘의 시간 복잡도는 O(VE)로, 여기서 V는 정점의 수, E는 간선의 수를 의미한다. 이는 모든 간선에 대한 완화를 V-1번 수행하기 때문이다. 다익스트라 알고리즘에 비해 일반적으로 느리지만, 음의 가중치를 처리할 수 있고 구현이 비교적 단순하여 네트워크 라우팅 프로토콜이나 특정 금융 모델링 등 다양한 분야에서 활용된다.

너비 우선 탐색(BFS)은 가중치가 없거나 모든 간선의 가중치가 동일한 그래프에서 단일 출발점 최단 경로 문제를 해결하는 데 사용할 수 있는 간단하면서도 효율적인 알고리즘이다. 이 경우, 시작 정점에서 다른 정점까지의 최단 거리는 경로를 구성하는 간선의 개수에 비례하므로, BFS가 이를 정확히 계산할 수 있다.

BFS는 큐 자료구조를 활용하여 시작 정점을 기준으로 인접한 정점들을 차례대로 방문하며 거리를 갱신한다. 각 정점을 처음 방문할 때의 거리가 해당 정점까지의 최단 거리가 된다. 이 과정은 모든 정점을 방문하거나 목표 정점을 찾을 때까지 계속된다.

이 알고리즘의 시간 복잡도는 인접 리스트로 그래프를 표현했을 때 O(V+E)로, 다익스트라 알고리즘이나 벨만-포드 알고리즘에 비해 매우 빠르다. 따라서 가중치가 없는 그래프나 모든 간선의 가중치가 1과 같이 동일한 무향 그래프 및 유향 그래프에서 최단 경로를 구할 때 널리 사용된다.

BFS는 네트워크 라우팅, 소셜 네트워크 분석, 퍼즐 게임의 해 탐색 등 다양한 응용 분야에서 최단 경로 또는 최소 단계를 찾는 기본 도구로 활용된다.

모든 쌍 최단 경로 문제는 그래프 상의 모든 정점 쌍 사이의 최단 경로를 찾는 문제이다. 이는 단일 출발점 최단 경로 문제가 하나의 시작점에서 다른 모든 점까지의 거리를 구하는 것과 달리, 그래프 내 모든 가능한 출발점과 도착점의 조합에 대한 최단 거리를 계산한다는 점에서 차이가 있다. 이 문제는 네트워크 분석, 운송 경로 최적화, 지리 정보 시스템 등 광범위한 분야에서 활용된다.

이 문제를 해결하는 대표적인 알고리즘으로는 플로이드-워셜 알고리즘이 있다. 이 알고리즘은 동적 계획법을 기반으로 하며, 음의 가중치를 가진 간선이 존재해도 사이클이 없는 한 정확한 결과를 계산할 수 있다. 다른 접근법으로는 각 정점을 차례로 시작점으로 하여 다익스트라 알고리즘이나 벨만-포드 알고리즘을 반복적으로 적용하는 방법도 있다. 특히 그래프의 가중치가 모두 음수가 아닐 경우, 다익스트라 알고리즘을 모든 정점에 대해 수행하는 것이 효율적일 수 있다.

이 문제의 결과는 보통 거리 행렬 형태로 표현되며, 각 행렬 요소는 특정 출발 정점에서 도착 정점까지의 최단 거리 값을 담는다. 또한, 최단 경로 자체를 재구성하기 위한 경로 행렬을 함께 구하는 경우도 많다. 모든 쌍 최단 경로 문제의 해법은 운송 계획, 통신 네트워크의 라우팅 프로토콜 설계, 게임 프로그래밍에서의 인공지능 경로 탐색 등 복잡한 시스템의 기초를 이루는 중요한 도구로 사용된다.

음의 가중치는 그래프의 간선에 할당된 비용이 음수인 경우를 가리킨다. 이는 실제 문제를 모델링할 때 이익, 감소, 역방향 흐름 등을 표현하는 데 사용될 수 있다. 예를 들어, 물류 네트워크에서 특정 구간을 통과하면 비용이 절감되는 상황이나, 금융 거래에서 환율 변동에 따른 손실을 나타낼 때 음의 가중치가 적용된다.

그러나 음의 가중치는 최단 경로 문제를 푸는 알고리즘에 큰 영향을 미친다. 대표적인 다익스트라 알고리즘은 모든 간선의 가중치가 음이 아니라는 전제 하에 동작한다. 음의 가중치가 존재하면 알고리즘이 잘못된 결과를 내거나 무한 루프에 빠질 수 있다. 이는 알고리즘이 한 번 방문한 정점의 거리를 갱신하지 않는 탐욕 알고리즘 방식이기 때문이다.

음의 가중치를 포함한 그래프에서 단일 출발점 최단 경로 문제를 해결하려면 다른 접근법이 필요하다. 벨만-포드 알고리즘은 음의 가중치를 처리할 수 있는 대표적인 알고리즘이다. 이 알고리즘은 모든 간선을 반복적으로 완화하여 최단 거리를 점진적으로 개선하며, 음의 가중치 순환이 존재하는지도 감지할 수 있다.

음의 가중치 순환이란 그래프에서 어떤 사이클을 따라 이동했을 때 전체 경로의 가중치 합이 음수가 되어, 경로를 반복할수록 거리가 무한히 감소하는 상황을 말한다. 이러한 순환이 시작 정점에서 도달 가능하다면 유한한 최단 경로가 존재하지 않게 되며, 벨만-포드 알고리즘은 이를 발견하고 보고한다.

단일 출발점 최단 경로 문제를 해결하는 알고리즘들은 종종 최단 경로 트리를 생성한다. 이는 주어진 시작 정점을 루트로 하여, 해당 정점에서 그래프의 다른 모든 정점까지의 최단 경로를 포함하는 부분 그래프이며, 일반적으로 트리의 구조를 가진다. 이 트리는 시작 정점에서 다른 모든 정점으로 가는 유일한 최단 경로를 나타낸다.

최단 경로 트리는 각 정점이 자신의 부모 정점을 가리키는 선행자 배열이나 맵을 통해 효율적으로 표현된다. 예를 들어, 다익스트라 알고리즘이나 벨만-포드 알고리즘을 실행한 후, 각 정점에 대해 최단 경로 상에서 자신 바로 앞에 오는 정점(부모 정점)을 기록하면, 이를 역추적하여 시작 정점부터 해당 정점까지의 전체 경로를 재구성할 수 있다. 이렇게 연결된 부모-자식 관계는 하나의 트리를 형성한다.

이 트리는 단순히 거리 값만을 계산하는 것보다 더 풍부한 정보를 제공한다. 네트워크 라우팅 프로토콜에서 데이터 패킷의 전송 경로를 결정하거나, 내비게이션 시스템에서 경로 안내를 생성하는 등 실제 응용에서 경로 자체를 시각화하거나 활용해야 할 때 필수적이다. 또한, 알고리즘의 정확성을 증명하거나 분석하는 데 있어서도 중요한 개념적 도구로 사용된다.

단, 모든 정점에 도달 가능한 경우에만 완전한 트리가 형성된다. 또한 그래프에 음의 가중치 순환이 존재하여 특정 정점까지의 최단 거리가 정의되지 않는 경우, 또는 동일한 최단 거리를 가지는 서로 다른 경로가 여러 개 존재하는 경우에는 유일한 최단 경로 트리가 정의되지 않을 수 있다.