다익스트라 알고리즘 (Dijkstra Algorithm)
다익스트라 알고리즘은 최단 경로 문제를 해결할 수 있는 알고리즘이다.
최단 경로 알고리즘에는 BFS, 다익스트라, 플로이드와샬, 벨만-포드가 있다.
BFS는 간선의 가중치가 모두 같을 때, 다익스트라와 벨만-포드는 각 간선의 가중치가 다를 때 한 정점에서 다른 정점까지의 최단 경로를 구할 때(벨만-포드는 음의 가중치가 있을 때), 플로이드와샬은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구할 때 사용한다고 함.
알고리즘은 다음과 같은 순서를 통해 수행된다.
1. 시작 노드 설정
2. 최단 거리 테이블 초기화 (연결 되지 않은 노드는 INF)
3. 연결되었지만 방문하지 않은 노드 중 최단 거리를 가지는 노드 선택 & 방문
4. 해당 노드를 거쳐 다른 노드로 갈 때의 비용을 계산하여 최단 거리 테이블을 갱신한다.
모든 노드를 방문할 때까지 3,4번을 반복하면 된다!
예시를 들어보자.
우선 시작 노드인 정점 1을 기준으로 최단 거리 테이블을 초기화한다.
(연결된 노드는 해당 선의 가중치로, 연결되지 않은 노드는 INF로)
그 다음, 위 테이블에서 방문한 노드 (1번)을 제외하고 가장 작은 가중치를 가지고 있는 2번 노드를 선택한다.
2번 노드와 연결되어있는 노드 (1,3,4)가 이미 가지고 있는 가중치와 2번 노드의 가중치 + 선의 가중치 값을 비교해 작은것으로 업데이트한다. 여기서는 INF의 값을 가지고 있던 4번의 값이 6+14 = 20 으로 업데이트 되었다.
방문한 노드를 제외한 노드에서 가장 작은 가중치를 가지고 있는 노드 -> 3번
여기서 6번노드가 기존에 가지고 있던 값인 13과 새로운 값인 9를 비교해 9로 업데이트 되었다.
방문한 노드를 제외한 노드에서 가장 작은 가중치를 가지고 있는 노드 -> 6번
여기서 5번노드가 기존에 가지고 있던 값인 INF과 새로운 값인 17를 비교해 17로 업데이트 되었다.
그 후 5번 노드와 4번 노드를 차례로 방문하게 된다. 이때는 값이 업데이트 되지 않는다.
위 과정을 다음과 같은 코드로 나타낼 수 있다.
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
typedef long long ll;
ll n = 6;
//주어진 경로의 가중치. 연결 안 되어있으면 INF
ll arr[6][6] = {
{0, 6, 8, INF, INF, 13},
{6, 0, 9, 14, INF, INF},
{8, 9, 0, 10, INF, 1},
{INF, 14, 10, 0, 5, INF},
{INF, INF, INF, 5, 0, 8},
{13, INF, 1, INF, 8, 0},
};
bool visited[6]; //방문여부
ll d[6]; //최단경로
//방문할 노드 선택. 최소 가중치를 가지는 노드 번호 반환
ll getMinIndex() {
ll min = INF;
ll idx = 0;
for (ll i = 0; i < n; i++) {
if (d[i] < min && !visited[i]) {
min = d[i];
idx = i;
}
}
return idx;
}
//start:시작 노드.
//위에서 설명한대로이면 1 (코드에서는 0)을 주어야 위의결과를 얻는다.
void dijkstra(ll start) {
//d[] 초기화
for (ll i = 0; i < n; i++) {
d[i] = arr[start][i];
}
visited[start] = true;
for (ll i = 0; i < n - 2; i++) {
ll minIndex = getMinIndex(); //현재의 최단 경로 index
visited[minIndex] = true;
for (ll j = 0; j < 6; j++) {
if (!visited[j]) {
if (d[minIndex] + arr[minIndex][j] < d[j]) { //더 적은 최단 경로를 발견하면
d[j] = d[minIndex] + arr[minIndex][j]; //경로를 새롭게 설정
}
}
}
}
}
int main(void) {
dijkstra(0);
for (ll i = 0; i < n; i++) {
cout << d[i] << " ";
}
}
// 0 6 8 18 17 9
위 알고리즘의 시간복잡도는 O(N^2)이다. 정점이 무수히 많고 그에 비해 간선이 부족할 경우엔 매우 비효율적일 수 있다.
=> 우선순위 큐를 이용한 변형된 다익스트라 알고리즘 존재. 이 경우엔 시간복잡도가 O(N*logN)가 될 수 있다.
이 방법은, 기존 방식과 기본 방식은 동일하지만 최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐를 이용한 것이다. 최소힙을 사용한다.
간단히 과정을 소개하자면,
우선 최단거리 테이블을 INF로 초기화한다. (시작노드의 거리는 0으로)
{가중치, 시작노드 번호} 페어를 힙에 넣는다.
힙에 있는 페어를 꺼내어 "방문한 적이 없다면" 최단 거리 테이블을 업데이트할것인데, 얻은 것이 기존 값보다 작으면 테이블 업데이트 후 힙에 인접한 노드를 넣는다. 방문한 적이 있다면 그냥 버린다.
위 과정을 반복할 것이고, 힙에 남은 페어가 없다면 종료한다.
=> 말로 설명하기 어려우므로 아래 문제를 우선순위 큐를 이용해 풀어보겠다,
백준의 아래 문제를 풀어보자. (백준 1753 C++)
https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
해당 코드로 반례는 찾지 못했지만 BOJ 패스는 받지 못했다..ㅠㅠ 4%에서 시간초과가 발생한다. 그 이유는 더 알아봐야할 것 같다. => 아래에 새 코드 적어둠!!
#include <bits/stdc++.h>
#define INF 1e9
#define max_v 20'000 + 10
#define max_e 300'000 + 10
using namespace std;
typedef long long ll;
ll d[max_v]; // 최단 거리 테이블
ll V, E; // V:정점 수, E:간선 수
ll srt; // 시작 정점 번호
vector<pair<ll, ll> > edge[max_e]; // 간선 정보. idx:시작노드, pair<비용,도착노드>
priority_queue<pair<ll, ll>> pq; // 최단거리, 노드번호
void dijkstra(ll start) {
pq.push({ 0, start });
while (!pq.empty()) {
ll dist = pq.top().first;
ll cur = pq.top().second;
pq.pop();
//굳이 비교할 필요 없음(계산값이 현 값보다 클게 분명)
if (d[cur] < dist) {
continue;
}
//인접노드
for (ll i = 0; i < edge[cur].size(); i++) {
ll next = edge[cur][i].second;
ll cost = dist + edge[cur][i].first;
if (cost < d[next]) {
d[next] = cost;
pq.push({ cost,next });
}
}
}
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> V >> E >> srt;
// 최단 거리 테이블 초기화
for (ll i = 1; i < V+1; i++) {
d[i] = INF;
}
d[srt] = 0;
// 간선 정보
for (ll i = 0; i < E; i++) {
ll u, v, w;
cin >> u >> v >> w;
edge[u].push_back({ w, v });
}
dijkstra(srt);
//출력
for (ll i = 1; i < V + 1; i++) {
if (d[i] == INF) cout << "INF" << '\n';
else cout << d[i] << '\n';
}
}
백준에 질문한 결과,
<priority_queue에 거리를 그대로 pair의 첫 번째 인자로 넣게 되면 pq가 거리가 가장 가까운 정점이 아닌 가장 먼 정점을 먼저 뽑게 되어 시간 복잡도가 터지게 됩니다. 보통 pair로 최단경로를 구할 때 cost를 음수로 만들어 넣도록 가르치는 이유가 그것입니다.> 이란 답변을 얻었다...
공부하다가 cost를 음수로 저장한 코드는 보았지만 그 이유를 알지 못해 그냥 사용했던게 화근이었다... pq에저장할때 음수로 바꾸어 저장하니 패스를 받을 수 있었다!
#include <bits/stdc++.h>
#define INF 1e9
#define max_v 20'000 + 10
#define max_e 300'000 + 10
using namespace std;
typedef long long ll;
ll d[max_v]; // 최단 거리 테이블
ll V, E; // V:정점 수, E:간선 수
ll srt; // 시작 정점 번호
vector<pair<ll, ll> > edge[max_e]; // 간선 정보. idx:시작노드, pair<비용,도착노드>
priority_queue<pair<ll, ll>> pq; // 최단거리, 노드번호
void dijkstra(ll start) {
pq.push({ 0, start });
while (!pq.empty()) {
ll dist = -pq.top().first;
ll cur = pq.top().second;
pq.pop();
//굳이 비교할 필요 없음(계산값이 현 값보다 클게 분명)
if (d[cur] < dist) {
continue;
}
//인접노드
for (ll i = 0; i < edge[cur].size(); i++) {
ll next = edge[cur][i].second;
ll cost = dist + edge[cur][i].first;
if (cost < d[next]) {
d[next] = cost;
pq.push({ -cost,next });
}
}
}
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> V >> E >> srt;
// 최단 거리 테이블 초기화
for (ll i = 1; i < V+1; i++) {
d[i] = INF;
}
d[srt] = 0;
// 간선 정보
for (ll i = 0; i < E; i++) {
ll u, v, w;
cin >> u >> v >> w;
edge[u].push_back({ w, v });
}
dijkstra(srt);
//출력
for (ll i = 1; i < V + 1; i++) {
if (d[i] == INF) cout << "INF" << '\n';
else cout << d[i] << '\n';
}
}
참고
https://yabmoons.tistory.com/364