[알고리즘] 최단 경로 알고리즘 비교 및 사용 케이스 정리

그래프 이론에서 최단 경로를 찾는 문제는 가중치가 존재하지 않는 그래프에서 가장 짧은 경로를 찾는 문제와 가중치가 존재하는 가중 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제로 나눌 수 있습니다. 이때 가중치의 경우 비용, 시간, 수수료 등의 이름으로 주어질 수 있으며 심지어 이러한 가중치들은 음수로 주어지는 경우도 존재합니다.

본 포스팅에서는 다양한 최단 경로 문제를 해결하기 위해 존재하는 여러 알고리즘에 대해 비교 분석하며 사용해야하는 케이스들을 정리하도록 하겠습니다. 그리고 각각의 알고리즘에 대한 자세한 내용과 코드 분석은 이후에 포스팅하도록 하겠습니다.

---

최단 경로 문제 종류

먼저 최단 경로 문제의 유형을 알아보도록 하겠습니다.

• 단일-출발(Single-Source) 최단 경로 : 단일 정점 v 에서 출발하여 나머지 모든 정점으로 도착하는 최단 경로를 구하는 문제입니다. 
• 단일-도착(Single-Destination) 최단 경로 : 모든 정점에서 출발하여 단일 정점 v 로 도착하는 최단 경로를 구하는 문제입니다. 그래프 내의 간선들을 뒤집으면 단일-출발 최단 경로 문제로 바뀔 수 있습니다.
• 단일-쌍(Single-Pair) 최단 경로 : 단일 정점 v 에서 다른 정점 v' 으로 가는 최단 경로를 구하는 문제입니다.
• 전체-쌍(All-Pair) 최단 경로 : 그래프 내의 모든 정점 쌍들의 최단 경로를 구하는 문제입니다.

위의 유형들은 모두 단일-쌍 방식으로 모든 최단 경로를 찾아가는 접근 방식으로도 해결이 가능하지만 각각의 유형에 맞는 알고리즘이 존재하며 훨씬 효율적이기 때문에 다양한 최단 경로 알고리즘을 숙지하고 유형에 맞게 적용하는 것이 중요합니다.

---

 최단 경로 알고리즘

지금부터 최단 경로 알고리즘 6가지에 대해 간략히 알아보도록 하겠습니다. 본 포스팅에서는 간단한 설명과 적용 케이스, 그리고 시간복잡도를 비교하도록 하겠습니다. 코드 구현과 상세 내용은 추후 각각의 주제로한 포스팅을 통해 링크를 삽입하도록 하겠습니다.

너비 우선 탐색(BFS, Breadth-First Search), 완전 탐색 알고리즘

가중치가 없거나 모든 가중치가 동일한 그래프에서 최단 경로, 즉 노드 간의 최소 이동 횟수를 구할 때 가장 효율적인 알고리즘입니다. 너비를 우선하여 완전 탐색을 통해 경로를 구하는 방식이며 가중치가 존재하지 않다면 위의 4가지 유형 모두에 적용할 수 있습니다.
시간 복잡도 : \( O(V+E) \) (인접리스트 구현)

https://devluce.tistory.com/17

[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 구현 꿀팁 아닌 꿀팁(?)

다익스트라(Dijkstra) 알고리즘

가장 많이 알려진 최단경로 알고리즘입니다. 구현 방식은 BFS와 비슷하며 각 정점을 최대 한번씩만 방문하여 연결된 정점이 더 적은 가중치일 경우 최저 가중치를 저장하는 테이블을 갱신해나가는 방식으로 체킹합니다. 또한 큐가 아닌 우선순위큐(힙)로 더 적은 가중치를 가진 간선을 먼저 탐색하는 방식으로 구현하면 수행시간을 더 효율적으로 개선할 수 있습니다. 다익스트라 알고리즘은 음이 아닌 가중 그래프에서의 단일-출발, 단일-도착, 단일-쌍 유형을 효율적으로 해결하는데 적용할 수 있는 알고리즘입니다.
시간 복잡도 : \( O(ElogV) \) (우선순위큐 적용)

벨만-포드(Bellman-Ford-Moore) 알고리즘

다익스트라 알고리즘이 각 정점을 최대 한번씩만 방문하여 최저 가중치를 갱신한다는 점때문에 음수 가중치가 존재하는 경우 무한히 마이너스로 갱신되는 음수 사이클의 존재를 확인할 수 없습니다. 따라서 음수 사이클의 존재 여부를 확인하기 위해 각 정점 탐색마다 모든 간선을 확인하는 과정이 존재하는 알고리즘이 바로 벨만-포드 알고리즘입니다. 마지막 정점에서 간선을 탐색할 때 가중치 저장 테이블이 갱신이 된다면 음의 사이클을 가지는 그래프로 판명되며 최단 경로를 파악할 수 없는 그래프로 리턴하게 됩니다. 벨만-포드 알고리즘은 음수 가중치를 가지는 그래프에서의 단일-출발, 단일-도착, 단일-쌍 유형을 효율적으로 해결하는데 적용할 수 있는 알고리즘입니다. 
시간 복잡도 : \( O(VE) \) 

플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜 알고리즘은 기본적으로 동적계획법으로 접근하며 모든 가능한 경유 정점에 대하여 시작점과 도착점을 모두 탐색하는 방식으로 구현하는 알고리즘입니다. 경유점, 시작점, 도착점을 모두 탐색한다는 특징 때문에 삼중 반복문으로 구현되며 해당 경로는 경유지로 거친 경로가 더 작은 경우에 갱신됩니다. 코드 구현이 매우 직관적이고 간단합니다. 플로이드-워셜 알고리즘은 전체-쌍 유형을 효율적으로 해결하는데 적용할 수 있는 알고리즘입니다. 음수 사이클의 존재 여부도 확인할 수 있어 음수 가중치를 가지는 그래프에도 적용할 수 있습니다.
시간 복잡도 : \( O(V^3) \)

에이스타(A*) 알고리즘

학부 게임프로그래밍 수업에서 배웠던 알고리즘입니다. 실제로 게임에서 주로 사용되는 최단 경로 알고리즘이며 다익스트라 알고리즘을 확장하여 만들어진 알고리즘입니다. 휴리스틱 추정 값이라는 다음 정점으로 향하는 예측 가중치를 더하여 우선순위큐에 저장합니다. 휴리스틱 추정 함수를 구현하여 다익스트라에 적용하면 에이스타 알고리즘이 되며 적절한 휴리스틱이 구현되면 탐색 속도가 향상됩니다. 에이스타 알고리즘은 휴리스틱 함수가 특정 목적지로 향하는 가중치를 추정하기 때문에 단일-쌍 유형만을 효율적으로 해결할 수 있는 알고리즘입니다.
시간 복잡도 : 휴리스틱 함수 구현에 따라 달라짐

SPFA(Shortest Path First) 알고리즘

SPFA 알고리즘은 벨만-포드 알고리즘의 비효율성을 개선시킨 알고리즘으로 가중치가 갱신된 정점에 대해서만 간선 탐색을 진행합니다. BFS 알고리즘과 비슷하게 큐를 사용하여 구현되며 실제로 모든 가중치가 동일하다면 BFS와 똑같이 작동하며 또한 다익스트라 알고리즘에서 우선순위큐 대신 큐를 사용하여 갱신된 정점만 큐에 삽입되게 구현한 알고리즘이라고 할 수 있겠습니다. 음수 가중치를 가지는 단일-출발, 단일-도착, 단일-쌍 유형에 벨만포드 알고리즘보다 더 효율적으로 적용 가능한 알고리즘입니다.
시간 복잡도 : 최악의 경우-\( O(VE) \) 일반적으로-\( O(V+E) \)

---

정리 및 결론

위의 내용을 표로 정리하면 다음과 같습니다.

알고리즘	적용 문제 유형	음수 가중치 가능 여부	시간 복잡도
너비 우선 탐색	가중치가 없거나 동일한 그래프	X (가중치 자체가 안됨)	\( O(V+E) \)
다익스트라	단일-출발, 단일-도착, 단일-쌍	X	\( O(ElogV) \)
벨만-포드	단일-출발, 단일-도착, 단일-쌍	O	\( O(VE) \)
플로이드-워셜	전체-쌍	O	\( O(V^3) \)
에이스타(A*)	단일-쌍	X	휴리스틱 함수 성능에 결정
SPFA	단일-출발, 단일-도착, 단일-쌍	O	\( O(VE) \), \( O(V+E) \)

본 포스팅에서는 여러 최단 경로 알고리즘을 분석하며 효율적으로 적용 가능한 문제 유형들을 정리해 보았습니다. 다익스트라 알고리즘의 경우 가장 일반적이며 최단 경로 알고리즘 파생의 기본이 되는 알고리즘이기 때문에 반드시 익혀 두는 것을 추천드립니다. 또한 에이스타 알고리즘의 경우 다익스트라가 실생활에서 적용하지 못하는 부분을 해결하는 알고리즘이며 이를 통해 실생활에서 가장 많이 파생되며 개발되고 있는 알고리즘이 에이스타 알고리즘입니다.
다양한 최단 경로 문제 상황과 문제마다 다르게 나오는 단어를 보고 해당하는 적절한 알고리즘을 적용하기 위해서는 최대한 많은 문제를 경험하고 접해보는 것이 중요한 것 같습니다. 

본 포스팅은 각각의 최단 경로 알고리즘의 포스팅을 업로드 할때 마다 업데이트하도록 하겠습니다.