최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다.
최단 경로 알고리즘에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다.
예를 들어
'한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우',
'모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'
등의 다양한 사례가 존재한다.
알고리즘 종류
- (1) 다익스트라 알고리즘, (2) 개선된 다익스트라 알고리즘
- 플로이드 워셜 알고리즘
- 벨만 포드 알고리즘
최단 경로 알고리즘은 그리디 + DP 알고리즘이 그대로 적용된다는 특징이 있다.
따라서 최단 경로 알고리즘은 그리디 및 DP 알고리즘의 한 유형으로 볼 수 있다.
다익스트라 방법 1
간단한 다익스트라 알고리즘 (구현하기 쉽지만 동작 속도가 느림)
다익스트라 알고리즘은 그래프에서 여러 개의 노드가 있을 때,
특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다.
현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.
원리
- 출발 노드를 설정한다
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 3, 4번 과정을 반복한다.
시간복잡도 :
V : 노드의 개수
cpp로 구현한 다익스트라1 :
#include <iostream>
#include <vector>
#define INF 1e9 // 10^9 == 10억 == 무한을 의미
using namespace std;
typedef struct dijkstra{
// 최단 거리 table
int dist;
// 거쳐온 직전 노드를 저장
int prev;
// 방문한 적이 있는지 체크
bool visited;
}Dijkstra;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int>> graph[100001];
// 노드 개수(n), 간선 개수(m), 시작 노드 번호(startv)
// 노드의 최대 개수는 최대 100,000라고 가정
int n, m, startv;
void init_dtable(Dijkstra* _dtable){
for (int i = 1; i <= n; i++)
{
_dtable[i].dist = 99;
_dtable[i].prev = -1;
_dtable[i].visited = false;
}
}
int getSmallestNode(Dijkstra* _dtable) {
int min = INF;
int ret = -1;
for (int i = 1; i <= n; i++)
{
if(_dtable[i].dist < min && _dtable[i].visited == false){
min = _dtable[i].dist;
ret = i; // 최단 거리가 가장 짧은 노드의 인덱스 반환
}
}
return ret;
}
void dijkstra(Dijkstra* _dtable) {
// 시작 노드 초기화
_dtable[startv].dist = 0;
_dtable[startv].prev = startv;
_dtable[startv].visited = true;
// 시작 노드와 연결된 노드들을 최단 거리 테이블에 update
for (int i = 0; i < graph[startv].size(); i++)
{
// graph[startv][i].first : startv와 연결된 노드
// graph[startv][i].second : startv와 연결된 노드까지 cost
_dtable[graph[startv][i].first].dist = graph[startv][i].second;
_dtable[graph[startv][i].first].prev = startv;
}
while(1){
// 현재 최단 거리가 가장 짧은 노드를 꺼내옴.
int now = getSmallestNode(_dtable);
// 최단 거리를 다 구했으면 종료
if(now == -1){
break;
}
_dtable[now].visited = true;
// 현재 노드와 연결된 다른 노드들 update
for (int i = 0; i < graph[now].size(); i++)
{
int cost = _dtable[now].dist + graph[now][i].second;
if(cost < _dtable[graph[now][i].first].dist) {
_dtable[graph[now][i].first].dist = cost;
_dtable[graph[now][i].first].prev = now;
}
}
}
}
void showMap(Dijkstra* _dtable, int _startv, int _endv){
int current = _endv;
while(current != _startv){
cout << current << " <- ";
current = _dtable[current].prev;
}
cout << current;
}
int main(void){
cin >> n >> m >> startv;
Dijkstra* dtable = new Dijkstra[n+1];
init_dtable(dtable);
// 모든 간선 정보 입력받기
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
// nodeA에서 nodeB로 가는 비용 C
graph[a].push_back({b,c});
}
dijkstra(dtable);
// 모든 노드로 가기 위한 최단 거리 출력
for (int i = 1; i <= n; i++)
{
if(dtable[i].dist == INF){
cout << "INF" << endl;
}
else {
cout << dtable[i].dist << " ";
}
}
cout << endl;
// node1에서 node6까지 가는 최단 경로
showMap(dtable, startv, 6);
return 0;
}다익스트라 방법 1 단점 :
최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하기 때문에 시간 복잡도가 이다.
따라서 문제에서 전체 노드의 개수가 5,000개 이하라면 방법 1로 풀 수 있지만,
노드의 개수가 10,000개를 넘어간다면 방법 1로는 문제를 해결하기 어렵다.
노드의 개수 및 간선의 개수가 많을 때는 '개선된 다익스트라 알고리즘(방법2)'를 이용해야 한다.
다익스트라 방법 2
개선된 다익스트라 알고리즘 (구현하기가 보다 까다롭지만 동작 속도가 빠름)
힙(Heap)
힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나이다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.
python에서는 우선순위 큐가 필요할 때 PriorityQueue 또는 heapq를 사용할 수 있다.
이 두 라이브러리는 우선순위 큐 기능을 지원한다.
다만 일반적으로 heapq가 더 빠르게 동작하기 때문에 수행 시간이 제한된 상황에서는 heapq를 사용하는 것이 좋다.
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 힙(heap) |
원리
개선된 다익스트라 알고리즘에서는 힙(Heap)자료구조를 사용한다.
힙 자료구조를 사용하면
특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로
출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.
최단 거리를 저장하기 위한 최단 거리 테이블은 다익스트라1과 같이 그대로 사용하고,
현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 사용한다.
시간복잡도 :
V : 노드의 개수
E : 간선의 개수
cpp로 구현한 다익스트라2 :
#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;
typedef struct dijkstra {
int dist;
int prev;
}Dijkstra;
typedef pair<int, int> pair_ii;
// 노드의 개수(n), 간선의 개수(e), 시작 노드
int n, e, startv;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair_ii> graph[100001];
// 두번째 원소(거리) 기준으로 min heap
struct cmp {
bool operator() (pair_ii& _a, pair_ii& _b) {
if(_a.second < _b.second){
return false;
}
return true;
}
};
void init_dtable(Dijkstra* _dtable){
// node가 1부터 시작하니까 1~n
for (int i = 1; i <= n; i++)
{
_dtable[i].dist = INF;
_dtable[i].prev = -1;
}
}
void doDijkstra(Dijkstra* _dtable) {
// <노드, 거리> 쌍을 값으로 갖는 priorityQ 생성
// 두번째 인자(거리정보) 기준으로 min heap(오름차순)
priority_queue<pair_ii, vector<pair_ii>, cmp> pq;
// 시작 노드로 가기 위한 최단 경로 0을 priortyQ에 push
pq.push({startv, 0});
_dtable[startv].dist = 0;
// cout << "test" << endl;
// pq가 빌 때까지 실행
while(!pq.empty()){
// 가장 최단 거리가 짧은 노드에 대한 <노드, 거리> 정보 pop
int node = pq.top().first;
int distance = pq.top().second;
pq.pop();
// pop한 node가 이미 처리된 적이 있다면 무시
if(_dtable[node].dist < distance) {
continue;
}
// 현재 노드와 연결된 다른 인접한 노드들 확인
for (int i = 0; i < graph[node].size(); i++)
{
int cost = distance + graph[node][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 update
if(cost < _dtable[graph[node][i].first].dist) {
_dtable[graph[node][i].first].dist = cost;
_dtable[graph[node][i].first].prev = node;
pq.push(make_pair(graph[node][i].first, cost));
}
}
}
}
void showMap(Dijkstra* _dtable, int _startv, int _endv){
int current = _endv;
while(current != _startv){
cout << current << " <- ";
current = _dtable[current].prev;
}
cout << current;
}
int main(void){
cin >> n >> e >> startv;
Dijkstra* dtable = new Dijkstra[n+1];
init_dtable(dtable);
// 모든 간선 정보를 입력받기
for (int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({b, c});
}
doDijkstra(dtable);
// 모든 노드로 가기 위한 최단 거리 출력
for (int i = 1; i <= n; i++)
{
if(dtable[i].dist == INF){
cout << "INF" << endl;
}
else {
cout << dtable[i].dist << " ";
}
}
cout << endl;
// node1에서 node6까지 가는 최단 경로
showMap(dtable, startv, 6);
return 0;
}플로이드 워셜 알고리즘 (Floyd-Warshall-Algorithm)
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
원리 :
플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
다만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
다익스트라 알고리즘은 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 사용했는데,
플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 거리를 저장하기 위해서 2차원 리스트에 최단 거리를 저장한다.
각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다.
예를 들어 1번 노드에 대해서 확인할 때는
A -> 1 -> B로 가는 비용을 확인한 후에 최단 거리 갱신.
점화식 :
'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신.
시간 복잡도 :
노드의 개수가 N개일 때,
알고리즘 상으로 N번의 단계를 수행하며, 각 단계마다 의 연산을 통해 '현재 노드를 거쳐가는'모든 경로를 고려한다.
따라서 총시간 복잡도는 이다.
cpp로 구현한 Floyd-Warshall
#include <iostream>
#include<iomanip>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(E)
int n, e;
int main(void) {
cin >> n >> e;
// 2차원 배열(그래프 표현)를 만들기
int** graph = new int*[n+1];
// 최단 거리 테이블을 모두 무한으로 초기화
for (int i = 0; i < n+1; i++) {
graph[i] = new int[n+1];
fill(graph[i], graph[i] + (n+1), INF);
}
// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (a == b) graph[a][b] = 0;
}
}
// 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for (int i = 0; i < e; i++) {
// A에서 B로 가는 비용은 C라고 설정
int a, b, c;
cin >> a >> b >> c;
graph[a][b] = c;
}
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
cout << "-----------\n";
// 수행된 결과를 출력
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (graph[a][b] == INF) {
cout << "INF" << ' ';
}
else {
cout << setw(3) << graph[a][b] << ' ';
}
}
cout << '\n';
}
for (int i = 0; i < n+1; i++) {
delete[] graph[i];
}
delete[] graph;
}벨만 포드 알고리즘
음수 간선이 포함된 상황에서의 최단 거리 문제를 풀 때 벨만 포드 알고리즘이 필요하다.
음수 간선이 포함된다면 다익스트라 알고리즘처럼 최소 비용을 구할 수 있을 것이다.
하지만 음수 간선 cycle이 발생한다면? 음의 무한인 노드가 발생한다!!
아래 예시의 경우 node1에서 node2로 가는 경우를 생각해보면
node1 -> node3 -> node5 -> node2 -> node3 -> node5 -> node 2 -> ...
이처럼 (node3 -> node5 -> node2)는 총 비용이 -1이므로 무한대로 최소 비용을 갱신하며 음의 무한대가 될 수 있다.
원리 :
- 출발 노드를 설정한다
- 최단 거리 테이블을 초기화한다
- 다음의 과정을 N-1번 반복한다
1) 전체 간선 E개를 하나씩 확인
2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
만약, 음수 간선 순환이 발생하는지 체크하고 싶다면 3. 과정을 한 번 더 수행.
수행 후 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것.
시간복잡도 :
로 다익스트라 알고리즘에 비해 느리다.
python으로 구현한 벨만 포드 :
import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드의 개수, 간선의 개수를 입력
v, e = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (v + 1)
# 모든 간선의 정보 입력
for _ in range(e):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미 (a -> b 의 비용이 c)
edges.append((a, b, c))
def bellman_ford(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
# 전체 v - 1번의 라운드(round)를 반복
for i in range(v):
# 매 반복마다 '모든 간선'을 확인한다.
for j in range(e):
cur_node = edges[j][0]
next_node = edges[j][1]
edge_cost = edges[j][2]
# 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
distance[next_node] = distance[cur_node] + edge_cost
# v번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
if i == v - 1:
return True
return False
# 벨만 포드 알고리즘 수행
negative_cycle = bellman_ford(1)
# 음수 순환이 존재하면 -1 출력
if negative_cycle:
print("-1")
else:
# 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
for i in range(2, v + 1):
# 도달할 수 없는 경우, -1 출력
if distance[i] == INF:
print("-1")
# 도달할 수 있으면 거리 출력
else:
print(distance[i])