c++/ 자료구조&알고리즘 개념 복습하기 - 23 / 다익스트라 알고리즘

< 다익스트라 알고리즘 >

• 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘
• 플로이드 워셜의 경우 음수의 간선은 괜찮고, 음수의 사이클이 존재하는 경우 문제가 발생
• but 다익스트라는 음수의 가중치를 가진 간선있으면 사용할 수 없다
• but 노드의 재방문을 허용하고 우선순위 큐를 사용한 방식의 경우 음수 가중치에 대한 최단 거리를 계산할 수 있으나 큰 오버헤드가 발생할 수 있다
  
  
• 바킹독님 강의링크
  (https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30)

---

< 구현 방식 (feat. 우선순위 큐) >

• 매번 아직 거리가 확정되지 않은 정점들 중에서 가장 가까운 정점을 찾아 최단거리를 확정한다

• 우선순위 큐를 활용해 구현해볼 수 있다

• 시간복잡도 : O(E * logE)
  
  

• 1. 우선순위 큐에 (0, 시작점)을 추가
• 2. 우선순위 큐에서 거리가 가장 작은 원소 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감(이미 해당 정점으로의 다른 최단 거리가 존재하고 있다)
• 3. 원소가 가리키는 정점을 v라고 할때, v와 이웃한 정점들에 대해 최단 거리 테이블 값(기존의 최단거리)보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가
• 4. 우선순위 큐가 빌 때까지 2,3번 과정을 반복

---

< 예제 - BOJ 1753 >

• https://www.acmicpc.net/problem/1753

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

#define INF 100000000

#define Dist first
#define Node second

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int V, E;
    cin >> V >> E;

    int S;
    cin >> S;

    vector<pair<int, int>> node[20005];                                                 
    // 그래프 정보 = index에 해당하는 정점으로부터 (거리, 정점번호) 저장
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // min heap
    // (시작점으로부터 거리, 정점 번호) 정보가 포함된다

    int minDistArr[200005]; // 시작점으로부터 최단거리 정보 테이블

    for (int i = 1; i <= V; i++)
    {
        minDistArr[i] = INF; // 초기에 최단거리 테이블 모두 INF 로 초기화
    }

    while (E--)
    {
        int u, v, w;
        cin >> u >> v >> w;

        node[u].push_back(make_pair(w, v));
    }

    minDistArr[S] = 0; // 시작 지점까지 거리는 0으로 초기화
    pq.push(make_pair(0, S));

    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();

        if (minDistArr[cur.Node] != cur.Dist)
            continue; // 시작점에서 cur.Node 로의 다른 최단 거리가 존재하므로 넘어간다
            
            // 현재 턴의 정점까지 거리가 최단거리라면 
            //이 정점을 통해 다른 곳 까지의 최단거리를 만들 수 있는지 검사하는 것
            
        for (auto next : node[cur.Node])
        { // cur.Node 에 연결된 정점 살피기
            if (minDistArr[cur.Node] + next.Dist >= minDistArr[next.Node])
                continue;
            // 거쳐서 가는것보다 기존 최단거리가 더 짧으면 넘어간다
            // next.Dist = cur 에서 next 사이 간선 가중치

            minDistArr[next.Node] = minDistArr[cur.Node] + next.Dist; // 최단거리 갱신
            pq.push(make_pair(minDistArr[next.Node], next.Node)); // 우선순위 큐에 추가
        }
    }

    for (int i = 1; i <= V; i++)
    {
        if (minDistArr[i] == INF)
            cout << "INF\n";
        else
            cout << minDistArr[i] << "\n";
    }

    return 0;
}

---

< 최단경로 복원하기 >

• 각 정점별로 해당 정점으로 가기위해 그전에 어떤 정점을 거쳐야 하는지 정보를 가지고 있는지를 1차원 배열로 저장한다

while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();

        if (minDistArr[cur.Node] != cur.Dist)
            continue;
            
        for (auto next : node[cur.Node])
        { 
            if (minDistArr[cur.Node] + next.Dist >= minDistArr[next.Node])
                continue;

            minDistArr[next.Node] = minDistArr[cur.Node] + next.Dist; // 최단거리 갱신
            pq.push(make_pair(minDistArr[next.Node], next.Node)); // 우선순위 큐에 추가
            
            pre[next.Node] = cur.Node;
            // 시작점에서 next.Node 최단으로 가는 경우
            // next.Node 도달하기 전 단계에 cur.Node를 거친다!
        }
    }

---