최단경로 문제
이전부터 계속 그래프 문제를 해결하고 있는데 그래프에서 정말 많이 나오는 문제가 최단경로 문제라 하나씩 정복해나가고자 한다.
최단경로 문제에는 크게 플로이드 워샬, 벨만포드, 그리고 다익스트라 알고리즘이 있는데
제일 헷갈리는 부분이 다익스트라라서 문제를 푸는김에 정리해보려 한다.
다익스트라 알고리즘이란?
다익스트라라는 이름은 컴공생이라면 정말정말 많이들어봤는데 툭하면 이사람이 만들었단다
나는 시스템에서 semaphore를 Dijkstra가 만들었다는 것을 듣고 충격이었다. 대단하군
아무튼 다익스트라 알고리즘은 그래프에서 한 정점부터 다른 정점까지의 최단 경로를 찾는데 사용한다.
단 주의해야 할점은 모두 양수의 비용을 가져야 한다는 점이다.
음수의 비용을 가진다면 벨만포드 알고리즘을 사용해야 하겠다.
그리디 알고리즘
이전에 그리디 알고리즘에 대해 정리를 했었는데
사실 다익스트라 알고리즘도 그리디 알고리즘의 일종이다.
그리디 알고리즘은 각 단계에서 최적의 선택이 곧 전체의 최적의 해를 만든다는 것을 기본으로 하는데
다익스트라 알고리즘 역시 각 단계에서 최소 min 값을 찾기 때문이다.
그렇다면 어떻게 가장 좋아 보이는 선택을 하는지 작동 방법을 알아 보자.
다익스트라 알고리즘 작동방식
- 모든 정점까지의 거리를 무한대로 설정 (테이블 초기화)
- 시작 정점 0으로 설정
- 방문하지 않은 노드중 최단 거리의 노드 선택
- 해당 노드에서 다른 노드들로 가는 거리들로 테이블 갱신
- 반복
의 방법으로 작동하게 된다.
먼저 모든 정점까지의 거리를 가지는 노드 개수 크기의 배열을 만들어야 하는데 마치 DP 알고리즘 같다.
이러한 그래프가 있다고 가정해보자
제일먼저 1번으로 테이블을 초기화 시켜주어야 한다.
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 거리 | 무한대 | 무한대 | 무한대 | 무한대 | 무한대 | 무한대 |
시작노드 : 0번으로 설정하겠다.
시작노드가 0번이기 때문에 0번 노드의 비용을 0으로 설정해준다.
그리고 0번을 방문처리해주도록 한다.
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 비용 | 0 | 무한대 | 무한대 | 무한대 | 무한대 | 무한대 |
0번과 연결되어 있는 노드는 3개로 1, 2, 4번이 있다.
각 1, 2, 4번으로 갈 수 있는 비용을 더해서 테이블을 업데이트 해준다.
1번 : 현재 비용(0) + 간선 비용(1) = 1
2번 : 현재 비용(0) + 간선 비용(1) = 1
4번 : 현재 비용(0) + 간선 비용(5) = 5
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 비용 | 0 | 1 | 1 | 무한대 | 5 | 무한대 |
이후 테이블에서 가장 비용이 적은 노드를 방문한다
여기서는 1번노드를 방문하겠다.
1번노드와 연결되어 있는 노드는 2, 3번 노드이다.
이제 2, 3번 노드의 테이블을 업데이트 하면 되는데 아까 전에 이미 2번 노드를 업데이트 했었다!!
그렇다면 원래 저장되어 있는 것과 이번에 저장할것을 비교해서 더 작은 값으로 업데이트 하면된다.
2번 노드 : 현재 비용(1) + 간선 비용 (2) = 3
3번 노드 : 현재 비용(1) + 간선 비용 (3) = 4
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 비용 | 0 | 1 | min(1, 3) | 4 | 5 | 무한대 |
2번 노드는 원래 저장되어 있던 1과 새로 저장할 3중에 1이 더작으므로 바꾸지 않고 그대로 둔다.
그 다음 노드는 가장 짧은 2번을 방문한다.
2번 노드와 연결되어 있는 부분은 0번, 1번, 4번 이다.
0번은 이미 했기 때문에 넘어가고
1번 노드 : 현재 비용 (1) + 간선 비용 (2) = 3
4번 노드 : 현재 비용 (1) + 간선 비용 (2) = 3
1번 노드는 현재 저장되어 있는 1이 더 작기 때문에 바꾸지 않는다.
4번 노드의 원래 저장되어 있는 값 5보다 현재 저장할 3이 더 작기 때문에 업데이트 해준다.
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 비용 | 0 | 1 | 1 | 4 | min(5, 3) | 무한대 |
그다음 비용이 작은 노드는 4번이므로 4번 노드를 방문한다.
4번노드와 연결되어 있는 노드는 2, 3, 5번 노드이다.
2번 노드 : 현재 비용 (3) + 간선 비용(2) = 5
3번 노드 : 현재 비용 (3) + 간선 비용 (4) = 7
5번 노드 : 현재 비용 (3) + 간선 비용 (3) = 6
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 비용 | 0 | 1 | 1 | 4 | 3 | 6 |
2번노드, 3번노드는 현재저장되어 있는 값이 더 작기 때문에 바꾸지 않는다.
5번 노드는 6으로 업데이트 해준다.
그 다음 방문하는 노드는 3번노드이다.
3번노드는 1, 4, 5번 노드와 연결되어 있다.
1번 노드 : 현재 비용 (4) + 간선 비용 (3) = 7
4번 노드 : 현재 비용 (4) + 간선 비용 (4) = 8
5번 노드 : 현재 비용 (4) + 간선 비용 (1) = 5
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 비용 | 0 | 1 | 1 | 4 | 3 | min(6, 5) |
1번, 4번노드는 원래 있는 값이 더 작기 때문에 바꾸지 않고
5번노드는 기존 6에서 5로 바꾸어 준다.
5번 노드와 연결된 간선들은 이미 다 확인했기 때문에 테이블을 업데이트하지 않는다.
| 노드 | 0 | 1 | 2 | 3 | 4 | 5 |
| 비용 | 0 | 1 | 1 | 4 | 3 | 5 |
최종 비용 테이블은 위와 같을 것이다.
결론
가장 비용이 적은 노드 부터 방문하기 때문에 그리디 알고리즘의 일종이고
시작노드부터 모든 노드들에게 도착하는 비용을 계산할 수 있다.
어떤 문제에서 다익스트라 알고리즘을 써야하는가?
- 최단 경로 찾기
- N번째로 비용이 많이 드는 경로 찾기
이 때 중요한 점은 아까도 말했던 것처럼 음수가 아니어야 한다는 점이다!
또한 여러 경우의 수를 계속확인하기 때문에 N번째로 큰 비용은 몇이냐? 하는 문제도 가능하다.
다익스트라 알고리즘 장단점 / 시간복잡도
장점
- 최단 경로 빠르게 찾을 수 있음
단점
- 간선의 비용이 음수이면 사용 불가
- 모든 간선을 확인하기 때문에 최악의 경우 조금 느릴 수 있음
시간 복잡도
priority queue를 사용할때 기준으로
노드 수 V, 간선 수 E
O((V + E)log V) 이다.
C++ 다익스트라 알고리즘 구현 코드
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
int V = graph.size();
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(V, INF);
pq.push(make_pair(0, src));
dist[src] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
vector<pair<int, int>>::const_iterator it;
for (it = graph[u].begin(); it != graph[u].end(); ++it) {
int v = it->first; // vertex
int weight = it->second; // weight
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
return dist;
}
여기서 priority_queue가 작은순으로 될 수 있게 greater를 추가해 주는 부분을 주의해야 한다.
또한 큐에 넣는 pair는 (비용, 노드) 의 순으로 넣어야 한다는 점을 잊지말자
그 이후에는 큐에서 뺀 후 큐와 연결된 노드들을 모두 확인하고 그 다음 노드를 큐에서 빼는 식으로 진행하게 된다.
