Dijkstra [c++]

 - 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단 경로 탐색 알고리즘이다. 흔히 GPS 소프트웨어에서 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.

 - 다익스르타 알고리즘이 다이나믹 프로그래밍 문제인 이유는 "최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다." 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용 한다.

 

Ⅰ. 출발 노드를 설정한다.

Ⅱ. 출발 노드를 기준으로 각 노드의 최소비용을 저장한다.

Ⅲ. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

Ⅳ. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신하고 이를 3, 4번을 반복한다.

 

 

비용이 들어간 드래프

위와 같은 그래프는 컴퓨터 안에서 처리할 때 이차원 배열의 형태로 처리해야 한다.

 

위 정점과 cost를 이차원 배열 그래프 표로 나타낸 것

 

#include <iostream>

using namespace std;

int number = 6; // 정점의 갯수
int INF = 100001;

// 전체 그래프 초기화

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] = { false }; // 방문한 노드
int d[6]; // 각 노드 사이의 거리

int getSmallIndex() { // 가장 최소 거리를 가지는 정점을 반환
int min = INF;
int index = 0;
for (int i = 0; i < number; i++) {
if (!v[i] && min > d[i]) {
min = d[i];
index = i;
}
}
return index;
}

void dijkstra(int start) {
for (int i = 0; i < number; i++) {
d[i] = a[start][i]; // start 정점부터 i 정점까지의 거리를 d배열에 저장
}
v[start] = true; // start 방문표시
for (int i = 0; i < number - 2; i++) { // start 점과 마지막 점은 선택 안해도 되서 number-2 만큼 반복
int currentIndex = getSmallIndex(); // 가장 가까운 거리의 index 저장
v[currentIndex] = true; // 방문표시
for (int j = 0; j < number; j++) { // CurrentIndex 기준으로 최소거리 갱신
if (!v[j]) { // j점을 방문하지 않았고,
if (d[currentIndex] + a[currentIndex][j] < d[j]) { // (start에서 currentIndex 점을 지나서 다른 j점으로 가는 길이)가 start -> j 보다 더 짧다면
d[j] = d[currentIndex] + a[currentIndex][j];
}
}
}

cout << "현재 d : ";
for (int i = 0; i < number; i++) {
cout << d[i] << ' ';
} cout << endl;
}
}

int main() {
dijkstra(0);
for (int i = 0; i < number; i++) {
cout << d[i] << ' ';
}


return 0;
}