다익스트라 알고리즘

1. 개요

다익스트라 알고리즘은 1959년 다익스트라(Dijkstra)가 고안해낸 단일 출발점 최단경로 알고리즘이다. (Single-Source Shortest Paths)

다른 말로 가중치가 있는 방향그래프에서 임의의 두 노드 사이의 최단거리를 찾는 알고리즘이다. 

많은 다익스트라 알고리즘 중 가장 유명한 알고리즘이며, 최근에는 네트워크인 라우터가 패킷을 빠르게 전송하기 위해 다익스트라 알고리즘을 채택했다고 한다.

2. 알고리즘

A에서 F로 가는 최단거리를 찾아보자.

1. 초기화

시작 노드의 거리값은 0으로, 다른 노드들은 무한대로 초기화한다.

2. 루프

문제가 해결이 될 때 까지 무한루프를 돌며 다음 최소 값을 찾는다.

위의 상황에서 A가 출발점이고, A가 갈 수 있는 곳은 B C D이다.

그러므로 B를 10으로, C를 30으로, D를 15로 값을 재배정해준다.

그리고 A노드는 이미 지났으므로 Q 배열에서 빼서 S배열에 넣어준다.

이제 Q 집합에서 거리값이 가장 작은 놈을 찾아 위 내용을 반복해준다.

B,C,D,F,E 중에 가장 작은 놈은 B이므로 B를 선택한 후 위 과정을 반복한다.

B가 갈 수 있는 노드는 E이므로 E노드를 B + 20으로 설정한다. 만약 이미 값이 들어가 있다면 더 작은 값을 할당한다.

위 경우는 inf 보다 30이 더 작으므로 30을 할당한다. B의 값을 더하는 이유는 거리값이 초기 노드부터 시작했기 때문이다.

위와 같이 업데이트 과정을 Q 배열이 빌때까지 반복한다.

3. 정답

루플가 종료되면 S배열에는 {A,B,D,C,F,E}, 

A = 0

B = 10

C = 20

D = 15

E = 30

F = 25

Q = {}

로 남아있을 것이다.

A에서 F로 가는 것이므로 F의 거리값인 25를 손쉽게 찾을 수 있다.

4. 소스코드

//
// Created by 강경완 on 15. 12. 10..
//

#include 

using namespace std;

int path[100][100] = {0,};
int dis[100];
int Q[100] = {0,};
int n;

void init() {
    for (int i = 0; i <= n; i++) {
        dis[i] = 210000000;
    }

    for (int i = 1; i <= n; i++)
        Q[i] = i;
}

int min() {
    int m = 210000000;
    int t;
    for (int i = 1; i <= n; i++) {
        if (m > dis[Q[i]] && Q[i] != -1) {
            m = dis[Q[i]];
            t = i;
        }
    }
    return t;
}

bool chkEmpty() {
    for (int i = 0; i <= n; i++) {
        if (Q[i] > 0)
            return false;
    }
    return true;
}

int main() {
    int a, b, c, i, s, e, cnt;

    cin >> cnt;     // 입력 데이터 수
    cin >> n;       // 노드 수
    cin >> s >> e;  // 출발점, 도착점

    for (i = 1; i <= cnt; i++) {
        cin >> a >> b >> c;
        path[a][b] = c;
    }

    init();
    dis[s] = 0; // 처음 출발하는 dis는 0으로 셋팅 나머지는 전부 무한대로 초기화

    while (!chkEmpty()) {   // Q 배열이 비었는지 검사
        int m = min();      // Q 배열에서 거리값이 제일 작은 값을 가져옴
        int d;
        Q[m] = -1;          // Q 베열에서 제거
        for (int i = 1; i <= n; i++) {
            d = dis[m] + path[m][i];
            if (d < dis[i] && d != 0 && path[m][i] != 0) {
                dis[i] = d;
            }
        }
    }
    cout << dis[e] << endl;     // 도착지의 거리값을 출력
}

Sample Input

9

6

1 6

1 2 10

1 3 30

1 4 15

2 5 20

3 6 5

4 3 5

4 6 20

5 6 20

6 4 20

Output

25