다익스트라 알고리즘
그래프에서 최단 거리를 구하는 알고리즘이다.
시간 복잡도 : O(ElogV), (노드 수 : V, 에지 수 : E)
🧐 gif script)
시작점으로부터 조사하여, 최단 거리를 구한다.
😉 조건 및 수행 과정
시작점이 있으며, 음수 간선이 없는 경우에 사용한다.
😊 구현 코드(ex_1), ex_2))
ex_1) 단순 구현으로의 코드(리스트 기반, 시간 복잡도 : O(N^2))
- 거리에 START부터 연결된 것들의 간선을 d[i] 배열에 넣는다.
- getSmallIndex가 실행
2.1. current에 시작점에서 가장 가까운 노드의 index인 4가 대입된다.
"start에서 갈 수 있는 어떤 노드로 가는 값 중 최소 값"은 무조건 "시작점으로부터 최소의 거리"이기 때문이다(우선 첫 루프만 설명).- 따라서, v[4]는 방문처리한다. 그 후 방문된 것을 거쳐 갈 수 있는 노드를 조사한다.
- 원래부터 start에서 연결되었던(d에 원래 들어있던 값) '이 후 노드로의 거리' 값이 더 작은 값인지, '앞서 방문한 노드를 거쳐서 이 후 노드로 가는 거리 값'이 더 작은 값인지 비교한다.
- 4에서 더 작은 값을 d[j]에 저장해둔다. 4에서 비교한 두 경우 모두 결국에 최소 거리 값이 아닐 수도 있으나, 어차피 루프를 돌며 다른 경우도 다 조사하게 되므로 넘어가면 된다.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int number = 6;
int INF = 2147000000;
//전체 그래프를 초기화
int a[6][6] = {
{0, 2, 5, 1, INF, INF},
{2, 0, 3, 2, INF, INF},
{5, 3, 0, 3, 1, 5},
{1, 2, 3, 0, 1, INF},
{INF, INF, 1, 1, 0, 2},
{INF, INF, 5, INF, 2, 0},
};
//이미 방문한 노드 여부를 체크
bool v[6];
// 최단 거리를 저장하는 배열
int d[6];
//방문하지 않은 노드에서 가장 최소 거리를 지니는 정점을 반환
int getSmallIndex() {
int min = INF;
int index = 0;
for (int i = 0; i < number; i++) {
if (d[i] < min && v[i] == false) {
min = d[i];
index = i;
}
}
return index;
}
// 다익스트라 실행 함수
void dijkstra(int start) {
for (int i = 0; i < number; i++) {
d[i] = a[start][i];
}
v[start] = true;
for (int i = 0; i < number - 2; i++) {
int current = getSmallIndex();
v[current] = true;
for (int j = 0; j < 6; j++) {
if (v[j] == false) {
if (d[current] + a[current][j] < d[j]) {
d[j] = d[current] + a[current][j];
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
dijkstra(0);
for (int i = 0; i < number; i++) {
cout << d[i] << " ";
}
return 0;
}ex_2) 우선순위 큐로 구현한 코드(시간 복잡도 : O(ElogV), (노드 수 : V, 에지 수 : E))
ex_2.1) 잘못된 코드, 설명 부분은 아래 글과 주석으로 작성하였습니다.
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int number = 6;
int INF = 2147000000;
// 간선 정보를 저장하는 벡터
// 뒤에 int형 값 2개를 덧붙여야 하므로 a(7)이 아닌 a[7]로 지정한다.
vector<pair<int, int>> a[7];
// 최단 거리를 저장하는 벡터
vector<int> d(7);
// 다익스트라 실행 함수
void dijkstra(int start) {
// 시작점에서 시작점으로의 최소 거리는 0
d[start] = 0;
// min heap 구조, 더 작은 값을 기준으로 최상단 노드를 만들도록 한다.
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 출발 노드의 정보를 우선순위 큐에 넣는다.
pq.push(make_pair(startIndex, 0));//(ex_2.2.에서 변경되는 핵심 부분)
while (!pq.empty()) {
// 기준 점부터 가장 최소 거리 노드의 index (X)
int current = pq.top().first;
// 기준 점부터 가장 최소 거리 노드의 값 (X)
int distance = pq.top().second;
pq.pop();
// 최단 거리가 아닌 경우 스킵
if (d[current] < distance) continue;
for (int i = 0; i < a[current].size(); i++) {
// 선택된 노드의 인적노드
int nextIndex = a[current][i].first;
// 선택된 노드를 거쳐서 인접 노드로 가는 거리
int nextDistance = distance + a[current][i].second;
// 기존 최소 비용보다 더 작다면 교체
if (nextDistance < d[nextIndex]) {
d[nextIndex] = nextDistance;
// 그렇게 새롭게 갱신된 값을 넣어준다.
pq.push(make_pair(nextIndex, nextDistance));
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i <= number; i++) {
d[i] = INF;
}
// 1번 노드에서 2번 노드로 갈 때 필요한 거리가 2
a[1].push_back(make_pair(2, 2));
a[1].push_back(make_pair(3, 5));
a[1].push_back(make_pair(4, 1));
a[2].push_back(make_pair(1, 2));
a[2].push_back(make_pair(3, 3));
a[2].push_back(make_pair(4, 2));
a[3].push_back(make_pair(1, 5));
a[3].push_back(make_pair(2, 3));
a[3].push_back(make_pair(4, 3));
a[3].push_back(make_pair(5, 1));
a[3].push_back(make_pair(6, 5));
a[4].push_back(make_pair(1, 1));
a[4].push_back(make_pair(2, 2));
a[4].push_back(make_pair(3, 3));
a[4].push_back(make_pair(5, 1));
a[5].push_back(make_pair(3, 1));
a[5].push_back(make_pair(4, 1));
a[5].push_back(make_pair(6, 2));
a[6].push_back(make_pair(3, 5));
a[6].push_back(make_pair(5, 2));
dijkstra(1);
for (int i = 1; i <= number; i++) {
if (d[i] == INF) {
cout << "infinity" << '\n';
}
else {
cout << d[i] << '\n';
}
}
return 0;
}
위 코드는 ex_1)보단 낫고, 결과 값이 명확하게 나온다. 하지만 비효율적인 코드이다.
왜냐하면, 아래 코드는 방문 여부를 체크하지 않고, priority_queue의 first 부분에 최소 거리 노드의 index를 넣었기 때문이다.
first 부분인 노드의 index를 기준으로 오름차순으로 정렬이 되기 때문에, 기준으로서 큰 의미가 없어진다. 그렇게 들렀던 부분일지라도 하나하나 비교하게 되는 경우가 생길 수 있을 것이다.
따라서, distance를 기준으로 정렬될 수 있도록 pq.first 부분에 최소 거리를, pq.second 부분에 최소 거리 노드의 index를 넣는 식으로 코드를 수정한다.
ex_2.2) 제대로 된 다익스트라 알고리즘 코드
void dijkstra(int startIndex) {
// 시작점에서 시작점으로의 최소 거리는 0
d[startIndex] = 0;
// min heap 구조, 더 작은 값을 기준으로 최상단 노드를 만들도록 한다.
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 출발 노드의 정보를 우선순위 큐에 넣는다.
pq.push(make_pair(0, startIndex));
// 우선순위 큐는 first 값을 기준 정렬되므로, 위와 같이 수정한다.
while (pq.empty()==false) {
// 기준 점부터 가장 최소 거리 노드의 index
int current = pq.top().second;
// 기준 점부터 가장 최소 거리 노드의 값
int distance = pq.top().first;
pq.pop();
// 최단 거리가 아닌 경우 스킵
if (d[current] < distance) continue;
// pq 내부에 여러 개가 들어가도록 하고, 위 코드에서 가장 최소에 대한 값을
// distance, current에 넣는다.
for (int i = 0; i < a[current].size(); i++) {
// 선택된 노드의 인적노드
int nextIndex = a[current][i].first;
// 선택된 노드를 거쳐서 인접 노드로 가는 거리
int nextDistance = distance + a[current][i].second;
// 기존 최소 비용보다 더 작다면 교체
if (nextDistance < d[nextIndex]) {
d[nextIndex] = nextDistance;
// 그렇게 새롭게 갱신된 값을 넣어준다.
pq.push(make_pair(nextDistance, nextIndex));
}
}
}
}군대 가기 전에 수강한 자료구조 수업에서 다익스트라 알고리즘을 들었던 기억이 있다. 근데 기억이 안나서 하나하나 쓰고 그리고 구현해보면서 이해하느라 시간이 좀 걸렸다.
복습이 필수일 듯..
참고 :
ex_1) 동빈나 네이버 블로그
gif) https://surfingthecode.com/5-dutch-programmers-you-should-know/
@sonyrainy
좋은 글 감사합니다. 자주 올게요 :)