[Shortest Path] Dijkstra Algorithm

이번에 준비한 알고리즘은 Shortest Path를 찾는 알고리즘인 Dijkstra Algorithm입니다!!

옛날에 처음 다익스트라 알고리즘 배웠을 때는 좀 노가다스럽게 배워서 엄청 어렵고 짜증난 알고리즘이었는데,

다시 공부하니까 참 쉽네요... 역시 가르치는 사람이 잘 해야하는건가..

아무튼! Dijkstra Algorithm은 BFS기반으로 Shortest Path를 찾는 알고리즘입니다. 절차를 설명하자면!

---

1. 탐색되지 않은 노드가 담긴 우선순위 큐로부터 다음 탐색 노드를 pop한다.
2. 탐색 노드의 주변 연결된 노드들에 대해서 거리를 비교해본다.
3. 여기서 비교란 기준 노드 탐색 노드 연결 노드의 거리값이 현재 연결 노드에 설정된 거리값보다 작은지 비교하는 것이다.
4. 작다면 연결 노드의 거리값을 재설정해준다.

---

이해가 되시나요? 생각보다 단순하게 비교하네요!! 한번 예시를 통해서 확인해봅시다.

이번에 사용할 예시입니다. 먼저 작은지 비교해야 하니까 첫번째 거리값은 INF로 초기화를 해주고,

예시를 보일 때 탐색이 끝난 노드는 회색빛, 현재 탐색 노드가 되는 친구는 주황빛으로 표시하였어요.

• Step #1

먼저 첫 번째 단계에선, 탐색의 시작이 되는 노드부터 진행됩니다. 저는 0번 노드부터 탐색을 시작했어요.

현재 탐색 노드는 0번 노드!! 탐색 노드 기준으로 1, 3번이 연결되어 있네요. 그러면 해당 노드의 거리값을 0번 노드의 거리값 + edge값과 비교해서 봅시다.

INF > 0 + 10 | INF > 0 + 5

자 그럼 기준에 맞게 되네요. 거리값 변경!

• Step #2

위에서 알고리즘의 절차를 보면 우선순위 큐로부터 다음 탐색 노드를 pop한다.라고 하였습니다. 우선순위 큐에는 각 노드가 들어가고 값은 거리값으로 됩니다. 그러면 거리값이 가장 작은 친구가 우선순위 큐에서 pop이 되겠네요!? 다음 탐색 노드는 3번 노드가 되겠네요.

여기서 특이점은 1번 노드가 되겠죠. 첫 번째 단계에서 1번 노드의 거리값은 10이었는데, 다시 계산해보니까 더 짧은 길이 있었네요.

이제 감이 오시나요?? 나머지 step들도 이미지로 알아봅시다.

• Step #3

• Step #4

• Step #5

그럼 코딩으로 넘어갑시다.

int Dijkstra(int visitNode)
{
    priority_queue<int, vector<int>, less<int>> nextQueue;
    visit[visitNode] = true;
    for(int check=0; check<5; check++)
    {
        //기존 check로 가는 길보다 visitNode를 통해 현재 길로 가는게 더 빠르면
        if((map[visitNode][check] != 0) && (path[check] > map[visitNode][check] + path[visitNode]))
            path[check] = map[visitNode][check] + path[visitNode];
        //아직 방문하지 않은 것들을 집어넣어
        if(visit[check] == false) nextQueue.push(check);
    }
    int nextN;
    if(nextQueue.empty()) nextN = INF;
    else                  nextN = nextQueue.top();
    return nextN;
}

먼저 남은 노드 들은 우선순위 큐에 들어가야 하니까 그에 대한 큐를 선언해주고, 탐색을 완료했다는 의미의 visit을 사용했습니다. 밑에 조건문을 보면 바로 알겠죠? 거리 비교 후에 더 짧은게 나오면 바로 수정. 전 다음 탐색할 노드를 반환하게 해서 main함수에서 하는 일을 좀 덜었어요. 

전체 코드는 여기있습니다. https://github.com/dinoHee/Dijkstra_Algorithm 

그럼 간단하게 마무리하겠습니다. ㅂㅂ~~