다익스트라(Dijkstra)란?
다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘 입니다. 즉 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려준다. -> ex) 인공위성
다만 음의 간선을 포함할 수 없으며, 현실에도 음의 간선은 존재하지 않기에 현실에서 사용하기 적합한 알고리즘 입니다.
예제1)
"1부터 다른 노드로 가는 최단 경로를 구해보자"
1. 1의 연결 노드는 2, 3, 4이며 각각 3, 6, 7로 산정할 수 있다.
0 | 3 | 6 | 7 |
위 그래프는 1, 2, 3, 4 다른 노드로 가는 비용을 정리한 것
2. 그럼 비용이 가장 저렴한 2번 노드로 가서 산정을 해본다. 이때 무한은 접근 할수가 없는 노드이다.
3 | 0 | 1 | 무한 |
이렇게 되면 3번 노드는 3 + 1로 이전에 있었던 6비용보다 4라는 비용으로 접근 할 수 있게 된다.
다시말해 다익스트라 알고리즘은 "현재까지 알고 있던 경로를 계속 갱신" 해서 최단 경로를 구하는 것이 다익스트라 알고리즘이라고 할 수 있다.
구체적인 작동과정
1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 설정
3. 방문하지 않은 노드중에서 가장 비용이 낮은 노드를 방문
4. 해당 노드를 거쳐서 가서 특정 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 과정에서 3, 4번을 반복작업.
예제2)
이러한 그래프는 컴퓨터의 2차원 배열로 처리되기에 바로 아래와 같이 각 노드마다 비용을 그래프로 산정해줍니다.
컬럼이 뜯하는 것은 왼쪽에서 차례대로 1, 2, 3, 4, 5, 6 노드의 비용을 산정.
로우는 기준 노드를 구분하기 위함입니다. (비용 == 0 ? 기준노드 : 노드)
0 | 2 | 5 | 1 | MAX | MAX |
2 | 0 | 3 | 2 | MAX | MAX |
5 | 3 | 0 | 3 | 1 | 5 |
1 | 2 | 3 | 0 | 1 | MAX |
MAX | MAX | 5 | 1 | 0 | 2 |
MAX | MAX | 5 | MAX | 2 | 0 |
그러면 순서대로 진행해보겠다.
"빨간 글자 = 순회한 노드."
"검은 글자 = 비용 갱신"
1. 1번 노드
가장 낮은 비용인 4번 노드로 이동
0 | 2 | 5 | 1 | MAX | MAX |
2. 4번 노드
가장 낮은 비용인 4번 노드로 이동 이때 3번 노드를 (1 + 3)으로 4로 단축, 5번 노드 조회 가능 그리고 가장 적은 노드인 2번 노드로 이동
0 | 2 | 4 | 1 | 2 | MAX |
3. 2번 노드
2노드를 거치더라도 갱신되는 것이 없음 그래서 배열은 유지하며 가장 비용이 적은 5노드로 이동합니다.
0 | 2 | 4 | 1 | 2 | MAX |
4. 5번 노드
이때 5를 거쳐서 3노드를 순회하는 것이 (1 + 1 + 1)3으로 단축, 6번 노드 조회 가능. 이때 가장 비용이 적은 3번 노드로 이동.
0 | 2 | 3 | 1 | 2 | 4 |
5. 3번 노드
비용 갱신이 일어나지 않는다.
0 | 2 | 3 | 1 | 2 | 4 |
5. 6번 노드
비용 갱신이 일어나지 않는다.
0 | 2 | 3 | 1 | 2 | 4 |
즉 최종결과는 이렇게 된다.
그럼 이것을 알고리즘으로 구현해보자.
구현에 앞서 위에서 말한 작동과정에 대해서 이해하고 빗대어서 생각하면 훨신 쉽게 이해할 수 있었다.
#include <iostream>
using namespace std;
int num = 6;
int MAX = 100000000;
int a[6][6] = {
{0, 2, 5, 1, MAX, MAX},
{2, 0, 3, 2, MAX, MAX},
{5, 3, 0, 3, 1, 5},
{1, 2, 3, 0, 1, MAX},
{MAX, MAX, 1, 1, 0, 2},
{MAX, MAX, 5, MAX, 2, 0},
};
bool v[6]; //방문한 노드 체크
int line[6]; //비용
int getSallIndex() {
int min = MAX;
int index = 0;
for(int i = 0; i < num; i++) {
if(line[i] < min && !v[i]) { //방문하지 않은 노드의 낮은 비용체크
min = line[i];
index = i;
}
}
return index;
}
void dijkstra(int start) {
//비용확인
for(int i = 0; i < num; i++) {
line[i] = a[start][i];
}
//1. 첫 노드 방문 체크
v[start] = true;
//num - 2를 하는 이유: 첫번째와 마지막 노드를 제외를 생각해서 시간 단축
for(int i = 0; i < num - 2; i++) {
int current = getSallIndex(); // 가장 비용이 저렴한 노드 추출
v[current] = true; //노드 방문 체크
for(int j = 0; j < 6; j++) {
if(!v[j]) { //방문이 안된 노드 체크
//t. a[current][j] = 선택한 노드에서 산정된 방문할 수 있는 노드의 비용
//선택한 노드의 비용과 t의 합을 산정해 기존의 비용과 비교
if(line[current] + a[current][j] < line[j]) {
//비교후 낮은 비용의 값을 선정
line[j] = line[current] + a[current][j];
}
}
}
}
}
int main() {
dijkstra(0);
for(int i = 0; i < num; i++) {
cout << line[i];
}
}
이렇게 해서
0 2 3 1 2 4로 비용갱신이 되어 최단경로를 찾은 것을 확인할 수 있다.
'알고리즘' 카테고리의 다른 글
알고리즘 - 플로이드-워셜(Floyd-Warshall) (1) | 2024.06.18 |
---|---|
[백준: 1339] 단어 수학 (발표자료) (2) | 2024.06.14 |
[백준: 6198] 옥상 정원 꾸미기 (0) | 2024.04.09 |
[백준: 9375] 패션왕 신해빈 (0) | 2024.04.08 |
[백준: 7785] 회사에 있는 사람 (0) | 2024.04.08 |