다익스트라 알고리즘이란?
다익스트라 알고리즘은 그래프의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘이다.
매번 최단 경로의 정점을 선택해 탐색을 반복한다.
그래프에서 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘 외에 벨만-포드 알고리즘, 프로이드 워샬 알고리즘이 있다.
다익스트라 알고리즘 동작
- 출발 정점을 선택한다.
- 최단 거리 테이블을 무한으로 초기화한다.
- 현재 정점와 인접한 정점 중 방문하지 않은 정점 중 거리가 가장 짧은 정점을 방문 후 방문 처리한다.
- 현재 정점을 거쳐 다른 정점으로 가는 가중치 값(출발 정점 ~ 현재 정점까지 거리 + 현재 정점 ~ 다른 정점까지 거리)을 갱신한다.
- 3~4 과정을 반복한다.
다익스트라 알고리즘 그림으로 알아보기
1~5 정점을 포함하는 그래프가 있다.
1~5 정점의 가중치 값인 distance 배열을 INF로 초기화 해준다.(기존 distance값보다 작은 값이 들어왔을 때 갱신해주기 위함)
1번 정점을 시작 정점이라고 했을 때 우리는 (1 -> 2), (1 -> 3), (1 -> 4), (1 -> 5)까지 각 최단 거리를 구해야한다.
시작 정점~시작 정점까지의 거리는 0이므로 1의 가중치 값을 0으로 갱신해주고 방문 처리를 한다.
1번 정점을 방문했다면 1번 정점과 인접한 정점들을 탐색한다.
이 때 인접 정점들은 2, 4, 5번이다.
2번 정점을 보면 distance[2](INF) > distance[1] + 5(5) 이므로 2번 정점까지의 최솟값을 5로 갱신해준다.
1번 정점과 인접한 2번 정점을 갱신했다면 이번에는 1번 정점과 인접한 4번 정점을 보자.
마찬가지로 distance[4](INF) > distance[1] + 9(9)이므로 4번까지의 최솟값을 9로 갱신해준다.
1번과 인접한 정점 2, 4정점을 갱신했다면 마지막 5번 정점을 보자.
distance[5](INF) > distance[1] + 1(1)이므로 5번까지의 최솟값을 1로 갱신해준다.
1번 정점과 인접한 정점의 갱신이 끝났다. 이제 distance배열을 탐색하여 방문하지 않은 정점 중 가중치가 가장 작은 정점을 방문한다.
1번 정점인 0은 이미 방문하였고 5, INF, 9,1 중 최솟값은 1, 즉 5번 정점이므로 5번 정점을 방문한다.(5번 정점 방문 처리)
이제 5번 정점과 인접한 정점 중 방문하지 않은 정점을 탐색한다.
5번 정점과 인접한 정점은 1, 4번 정점인데 1번 정점은 방문처리 되었으므로 4번 정점을 갱신할 준비를 한다.
distance[4](9) > distance[5] + 2(3)이므로 4번까지의 최솟값을 3으로 갱신해준다.
5번 정점과 인접한 정점의 갱신이 끝났다. 위와 마찬가지로 distance배열을 탐색하여 방문하지 않은 정점 중 가중치가 가장 작은 정점을 방문한다.
방문한 1번, 5번 정점을 제외하고 5, INF, 3중 최솟값은 3, 즉 4번 정점이므로 4번 정점을 방문한다.(4번 정점 방문 처리)
위 방식과 마찬가지로 distance[3](INF) > distance[4] + 6(9)이므로 3번까지의 최솟값을 9로 갱신 후 방문하지 않은 정점 중 최솟값인 2번 정점 방문 후 방문 처리해준다.
distance[3](9) > distance[2] + 2(7)이므로 3번까지의 최솟값을 7로 갱신 후 방문하지 않은 정점 중 최솟값인 3번 정점 방문 후 방문 처리해준다.
3번 정점과 인접한 방문을 탐색해야 하는데 이미 모든 정점의 방문이 완료된 상태이므로 종료한다.
소스 코드
코드 개선 : 위에서 distance 배열을 탐색하여 가중치가 최솟값인 정점을 방문한다고 하였다.
이 때 정점의 개수만큼 탐색을 진행하므로 정점의 개수가 많아질 수록 시간복잡도가 늘어난다.
따라서 반복문으로 최소 정점을 탐색하지 않고 최소 힙에 저장하여 효율적으로 코드를 개선할 수 있다.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef 2147000000 INF;
typedef pair<int, int> p;
vector<p> arr[20001];
int main() {
int V, E, K;
int u, v, w;
priority_queue<p> pQ; // first->가중치, second->정점
cin >> V >> E; // 정점 개수와 간선 개수
cin >> K; // 시작 정점
vector<int> res(V + 1, INF); // 모든 정점들의 가중치 0으로 초기화
for (int i = 0; i < E; i++) {
cin >> u >> v >> w;
arr[u].push_back(make_pair(w, v)); //간선 정보 저장(단 방향 그래프 형성)
}
pQ.push(make_pair(0, K)); // 시작 정점 K의 가중치를 0으로 설정하고 시작 정점 K를 최소 힙의 push
res[K] = 0;
while (!pQ.empty()) { //Q가 비어있지 않을 때까지(모든 정점을 방문하기 전까지)
int dis = -pQ.top().first; // 현재 정점의 가중치
int vertex = pQ.top().second; //현재 정점
pQ.pop();
if (res[vertex] < dis) // 방문을 했다면(만약, 방문을 한 상태라면 현재 가중치 값(dis)이
continue; // 이미 res에 저장된 값보다 작을 수 없음, 이전에 저장 한 값이 최단 경로이기 때문 )
for (int i = 0; i < arr[vertex].size(); i++) {
int nextDis = res[vertex] + arr[vertex][i].first; // 인접 정점
int nextVertex = arr[vertex][i].second; // 인접 정점까지 거리
if (nextDis < res[nextVertex]) { // 인접 정점을 방문하지 않았다면 갱신 후 힙에 저장
res[nextVertex] = nextDis;
pQ.push(make_pair(-nextDis, nextVertex));
}
}
}
for (int i = 1; i <= V; i++) {
if (res[i] == INF)
cout << "INF" << "\n";
else
cout << res[i] << "\n";
}
return 0;
}