다익스트라 알고리즘

Dynamic Programming(다이나믹 프로그래밍, 동적 계획법)을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. DP 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선을 포함할 수 없다. 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 매우 적합한 알고리즘 중하나라고 할 수 있다.

다익스트라 알고리즘이 DP 문제인 이유는 "최단 거리는 여러개의 최단거리로 이루어져 있기 때문이다". 즉, 작은 문제가 큰 문제의 부분집합에 속해있다. (작은 문제의 해가 큰 문제의 해가 된다.) 기본적으로 . 다익스트라는 하나의 최단거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.

1부터 다른 모든 노드로 가는 최단 경로를 구한다. 예를 들어 1->3 의 최소 비용은 6이다. 1에 당장 붙어있는 노드인 3까지 거리가 6이기 때문이다. 하지만, 이후에 노드 2까지의 최단 경로를 구했다면, 1->2->3 = 4로 6보다 더 저렴하다는 것을 알게 된다. 이 때, 현재까지 알고 있던 3으로 가는 최소 비용 6을 4로 새롭게 갱신한다. 다시 말해, 다익스트라 알고리즘은 '현재까지 알고 있던 최단 경로를 계속해서 갱신'한다.

컴퓨터는 당장 하나씩 밖에 계산하지 못하기 때문에 1->3 구하고 1->2 구하고, 최솟값 비교를 통해 1->2->3 이 최단 경로라는 것을 찾아낸다.

구체적인 작동 과정

1. 출발 노드 설정

2. 출발 노드 기준으로 각 노드의 최소 비용 저장

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

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신

5. 위 과정 3번 ~ 4번 반복

컴퓨터로 최소 비용을 구하기 위해서는 2차원 배열을 이용하여 처리할 수 있다. i행 j열 값은 i번 노드에서 j번 노드로 가는 비용을 의미한다.(배열은 0based index이지만, 여기서는 편의상 1부터 시작하는 것으로 한다.) =>일단 기본적으로 ∞값을 가지며, i->j로 가는 간선이 있다면(간선정보가 있다면) 그 값을 넣어준다.

행\열	1	2	3	4	5	6
1	0	2	5	1	∞	∞
2	2	0	3	2	∞	∞
3	5	3	0	3	1	5
4	1	2	3	0	1	∞
5	∞	∞	5	1	0	2
6	∞	∞	5	∞	2	0

1번 노드를 선택하여 1번과 연결된 3개의 간선을 확인 후, 1번에서 다른 정점으로 가는 최소 비용을 구해보면, 4번 노드이다. 따라서 4번 노드를 거쳐서 가는 경우(부분해)를 모두 고려하여 최소 비용 배열 값을 갱신하면 된다. visited = [1,4]

1-> 5 최소 비용 : ∞에서 2로 갱신! ∞이였지만 4를 거쳐서 5로 가는 경우는 비용이 2이므로, 1->5 최소 비용인 Arr[1][5]을 2로 갱신한다. 1 -> 3 최소 비용 : 5에서 4로 갱신! 5였지만 4를 거쳐서 3으로 가는 경우 비용이 4이므로 기존보다 더 작기 때문에 Arrr[1][3]을 4로 갱신한다. 갱신된 결과 배열(1행) 상태 :

1	2	3	4	5	6
0	2	4	1	2	∞

다음으로 방문하지 않은 노드 중에서 가장 비용이 작은 2 방문! visited = [1,4,2] 1 -> 2 최소 비용 : 2 그대로 유지 다음으로 방문하지 않은 노드 중에서 가장 비용이 작은 노드는 5번 노드이다! visited = [1,4,2,5] 1-> 3 최소 비용 : 4에서 3으로 갱신 1->4->3 = 1+3 = 4 에서 1->4->5->3 = 1+1+1 = 3. 기존 값보다 더 작기 때문에 Arr[1][3]을 3으로 갱신! 1->6 : ∞에서 4로 갱신! 1->5->6 = 1->4->5->6 = 1+1+2 = 4 다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드인 3번 노드 방문! visited = [1,4,2,5,3] 1->3 : 최소 비용 갱신X 마지막 6번 노드 방문! visited = [1,4,2,5,3,6] 1->6 : 최소 비용 갱신X

구현(C언어)

1. 배열

#include <stdio.h>
int numbeer = 6;
int INF = 10000000;
//전체 그래프 초기화
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 inidex = 0;
    for(int i=0;i<number;i++){
        if(d[i] < min && !v[i]) {
            min = d[i];//최소 거리 갱신
            index = i;//최소 거리 정점 번호 갱신
        }
    }
    return index;
}
void dikstra(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]){
                if(d[current] + a[current][j] < d[j]) {
                    d[j] = d[current] + a[current][j];
                }
            }
        }
    }
}
int main(void) {
    dijkstra(0);
    for(int i=0;i<number;i++){
        printf("%d",d[i]);
    }
}

코드 부연 설명 : 특정 정점 start에서 시작해서 최소 거리의 정점(current, 부분해)을 이용해서 n개 정점들 중 아직 방문하지 않은 노드(j)라면 [start -> current ->j] 을 구하고, 이것이 start->j 인 d[j]볻다 작으면 d[j]로 갱신한다! main에서는 특정 정점 start에서 각 노드까지 최단 거리를 각각 출력한다!

"작은 문제의 해가 큰 문제 해의 부분집합이 된다."는 DP 특성을 이용해서 특정 정점에서 다른 정점까지 최단 경로 구할 때, 특정 정점에서 최단거리 갖는 정점까지 거리(작은 문제의 해)를 이용해 특정 정점에서 다른 정점까지 최단 경로(큰 문제의 해, 최종 해)를 구할 수 있다! ex) A->F = 1 (부분해), A->C 최단 거리 = A->F->C = 1+1 = 2(최종해)

배열로 구현할 때 치명적 단점 시간 복잡도 : O(N^2). N개의 정점마다 반복적으로 수행하기 때문에 정점의 갯수는 많은데, 간선은 적을 때 비효율적으로 동작한다. =>힙을 이용하면 O(N*logN). start에서 다른 정점까지 최단 거리 정점 구하는 시간 복잡도 O(logN), N개 반복하기 때문에 O(N*logN) 거리 오름차순으로 힙이 구성된 최소힙으로 되어있나? 힙이 어떻게 구성되있길래 최단 거리 구하는 시간 복잡도가 logN이지? 일단 힙은 트리 구조이기 때문에 루트 노드-리프 노드 라고 해도 최대 logN임. 그러면 그래프의 정점 위치를 그대로 트리 구조로 하고, 거리 비교를 통해 최단 거리 갖는 정점 탐색하는 것은 별개인가? 우선순위 큐는 우선순위에 따라 루트 노드가 정해지는 건데 PQ가 왜 나오는 건가..!

2. 힙 구조의 우선순위 큐 & 인접리스트로 구현(C언어)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int number = 6; int INF = 10000000;
//편의상 인덱스는 1부터 사용할 것이기 때문에 정점 갯수+1 크기
vector<pair<int,int>> a[7];//간선 정보
int d[7];//최소 비용

void dikstra(int start){
    d[start] = 0;
    priority_queue<pair<int,int>> pg;//힙구조
    pq.push(make_pair(start,0));//start 정점에서 시작, s->s는 거리 0
    //가까운 순서대로 처리하기 때문에 큐 사용??!
    while(!pq.empty()){
        int current = pq.top().first();//pq에서 꺼낸 객체의 정점번호
        int distance = -pq.top().second();//거리값은 거리값인데 -?! => 짧은 것이 먼저 오도록 음수화?
        pq.pop();
        //최단거리가 아닌 경우 스킵
        if(d[current] < distance) continue;//같은 것을 비교하는 것 아닌가?
        for(int i=0;i<a[current].size();i++){//pq에서 뽑은 노드의 인접리스트 순회
            int next = a[current][i].first;//선택된 노드의 인접노드
            int nextDistance = distance + a[current][i].second;//선택된 노드를 인접노드로 거쳐서 가는 비용
            
            if(nextDistance <d[next]){
                d[next] = nextDistance;
                pq.push(make_pair(next,-nextDistance));
            }
        }
    }
}