[Graph] 다익스트라

다익스트라 알고리즘?

 그래프에서 노드들간의 최단 거리를 알아내기위해 사용하는 알고리즘이다.

다익스트라 알고리즘은 매우 직관적인 알고리즘이다. 그렇다면 다익스트라 알고리즘이 어떻게 동작하는지 알아보자.

 

---

IDEA

 예를 들어 아래와 같은 상황을 생각해보자.

지도

위 와같은 지도를 보자. 집에서 각각의 상점까지의 최단거리를 알아내고자한다. 이때 다익스트라 알고리즘을 사용하여 해결해보자.

 

1. 처음 집에서 출발을 한다.

1번 단계 지도

1번 단계 거리

집에서 처음 출발할때, 가지고 있는 정보는 집에서 집으로 갈 때, 0이라는 시간이 소요된다는 것 뿐이다. 

이제 집에서 바로 갈 수 있는 장소들에 대해 탐색해보자.

 

2. 

2번 단계 지도

2번 단계 거리

집에서 바로 갈 수 있는 장소들 중 상점, 영화관, 은행의 경우 기존의 거리(INF)보다

    집에서 집까지의 거리 + 집에서 각 위치들 까지의 거리

의 값이 더 짧다 따라서 위와 같이 업데이트 해준다.

 

3.

 그리고 집으로부터 가장 가까운 위치인 영화관으로 이동을 해서 위와 같은 탐색을 다시 반복해 준다.

3번 단계 지도

3번 단계 거리

이제 영화관에서 주변을 검색해보자.

영화관에서 집까지의 거리는 5이다. 그런데 여기서 주목해야할 부분이 있다.

집에서 영화관을 거쳐 은행까지가는 거리가 집에서 은행으로 가능 거리보다 짧다

 

    집에서 영화관 + 영화관에서 은행 < 집에서 은행

-->        5         +         8        = 13   <    17

 

즉 집에서 은행을 갈때에는 영화관을 거치는 것이 더 짦은 거리를 이용하는 것이므로 거리표를 업데이트 해준다.

 

그리고 영화관을 통한다면 집에서 햄버거 가게로 갈 수 있으므로 이 또한 업데이트 해준다.

 

4. 

 그 다음으로 집에서 가장 가까운 곳의 경우, 상점이다. 상점에서도 위와 같이 탐색해보자.

4번 단계 지도

4번 단계 거리

상점에서는 병원을 갈 수 있는데 병원의 경우 가본적이 없는 곳이므로 거리를 갱신해준다.

 

5.

 그 다음으로 가까운 곳은 햄버거집이다. 하지만 햄버거집에서 갈 수 있는 곳이 없으므로 넘어가자.

 

6.

 그 다음으로는 은행이 가깝다. 하지만 햄버거 집과 마찬가지로 갈 수 있는 곳이 없으므로 넘어간다.

 

7.

 은행의 경우 한번 들린 곳이므로 넘어간다.

 

8.

 마지막으로 가는 곳은 병원이다. 하지만 병원에서 갈 수 있는 햄버거집의 경우 기존에 탐색한 길이 더 짧으므로 탐색을 그만 둔다.

 

자, 그렇다면 위에서 알아본 원리로 코드를 작성해보자.

 

---

CODE

/*
    N : 노드 즉, 위치의 갯수
*/
vector<pair<int,int>> adj[N]; // first : 거리, second : to
int dist[N];
 
void init() {
    for(int i = 0 ; i < N ; i++) {
        dist[i] = INF;
    }
}
 
void dijkstra(int from) {
    init();
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Queue;
    Queue.push({0, from}); // from에서 from으로 가는 거리는 0이다.
    
    bool visited[N] = { false, };
 
    while(!Queue.empty()) {
        int now;
        
        /*
           만약 Queue가 비었거나 now가 이미 검색했던 곳이라면 from에서 now까지의            
          최단 거리는 탐색이 된 것이므로 넘어간다.
        */
        do {
            now = Queue.top().second;
            Queue.pop();
        } while (!Queue.empty() && visited[now]); 
        
        /*
            Queue를 모두 돌고 나온 now가 이미 탐색한 곳이면 탐색을 종료한다.
        */
        if( visited[now] == true) {
            continue;
        }
        visited[now] = true;
        
        /*
            now에서 바로 갈 수 있는 노드를 검색하여 이전에 탐색한 거리보다 짧은 거리가 나올 경우
            거리를 갱신해준다.
        */
        for(auto curr : adj[now]) {
            int nowToNext = curr.first;
             int next = curr.second;
            if(dist[next] > dist[now] + nowToNext) {
                dist[next] = dist[now] + nowToNext;
                Queue.push({dist[next], next});
            }
        }
    }
}

**수정 code 48번째 줄 오타 발견: 부등호 방향 수정