Algorithm

[Algorithm] 다익스트라(Dijkstra)

박땅콩 2022. 8. 23.

728x90

다익스트라 알고리즘을 공부한 내용을 바탕으로 작성한 내용입니다.

잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다!

다익스트라(Dijkstra)란?

하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 중 하나입니다.

도착 정점뿐만아니라 다른 모든 정점을 방문하며 각 정점까지의 최단 경로를 찾게됩니다.

동작 과정

1. 출발 정점과 도착 정점을 정합니다.

2. '최단 거리 테이블'을 초기화합니다.

3. 현재 정점에서 인접한 정점 중 방문하지 않은 정점들을 구별하고 방문하지 않은 정점들 중 가장 최단 거리의 정점을 선택합니다.

4. 해당 정점을 거쳐서 특정한 정점으로 가는 경우를 고려하여 최단 거리를 업데이트합니다.

5. 3~4번을 반복합니다.

동작 예시

출발 정점은 1번, 도착 정점은 5번이고 최단 거리 테이블을 전부 큰 값(무한대 INF)으로 초기화합니다.

간선 위의 숫자들은 거리(가중치)입니다.

출발 정점 1을 먼저 선택하고 최단 거리 테이블을 0으로 만들어줍니다.

1과 인접한 정점 중에서 방문하지 않았고 최단 거리를 가진 정점 2를 선택합니다.

1에서 정점 2까지 가는 거리를 계산하여 최단 거리 테이블을 2로 업데이트합니다. min(INF, 2)

1과 인접한 정점 중 방문하지 않았고 최단 거리를 가진 4번 정점을 선택합니다.

1에서 정점 4까지 가는 거리를 계산하여 최단 거리 테이블을 3으로 업데이트합니다. min(INF, 3)

4번 정점과 인접한 정점이고 방문하지 않은 3번 정점을 선택합니다.

1에서 4번 정점을 거쳐 3번 정점까지 가는 최단 거리를 5로 최단 거리 테이블을 업데이트합니다. min(INF, 5)

3번 정점과 인접한 정점이고 방문하지 않은 정점인 5번 정점을 선택합니다.

1에서 4번, 3번 정점을 거쳐 5번 정점까지 가는 최단 거리를 8로 최단 거리 테이블을 업데이트합니다. min(INF, 8)

최종적으로 1번 정점에서 5번 정점까지 오는데 최단 거리는 8입니다.

경로는 1 ➜ 4 ➜ 3 ➜ 5 입니다.

구현 : 우선 순위 큐(최소 힙)

거리 값을 담을 우선 순위 큐는 힙으로 구현합니다.

만약 최소 힙으로 구현한다면 부모(루트) 정점이 최소 거리를 가지게 됩니다.

C++에서는 #include <queue> 를 통해 우선 순위 큐를 사용할 수 있습니다.

그래서 최소힙으로 사용하기 위해선 아래와 같이 우선 순위 큐를 선언합니다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

이렇게 되면, 우선 순위 큐는 최소 거리를 가진 정점이 앞에 오게됩니다.

우선 순위 큐의 pair는 {거리, 정점 번호} 순입니다.

위 내용을 기반으로 다익스트라 알고리즘을 코드로 구현한다면, 아래와 같습니다.

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9 // 최댓값

int V; // 정점의 개수
int E; // 간선의 개수
int K; // 시작 정점
int M; // 도착 정점
vector<int> dist; // 최단 거리 테이블
vector<pair<int, int>> graph[20001]; // 연결 정점, 최소 거리

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 최소힙,  {최소거리, 정점} 적은 가중치가 맨 앞에 오도록 함

void dijkstra(int cur) {
    pq.push({0, cur});
    dist[cur] = 0;
    while(!pq.empty()) {
        int cur_node = pq.top().second; // 현재 정점
        int cur_dist = pq.top().first; // 현재 가중치
        pq.pop();
        for(pair<int, int> element : graph[cur_node]) {
            int next_node = element.first;
            int next_distance = element.second + cur_dist;
            if(next_distance < dist[next_node]) { // 다음 거리가 최단 거리 테이블에 저장된 다음 정점 값보다 작은 경우
                dist[next_node] = next_distance; // 업데이트
                pq.push({next_distance, next_node});
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> V >> E; // 정점의 개수, 간선의 개수
    cin >> K >> M; // 시작 정점, 도착 정점
    dist.resize(V + 1);
    for(int i = 0; i < E; ++i) {
        int start, end, dist;
        cin >> start >> end >> dist;
        graph[start].emplace_back(make_pair(end, dist));
    }

    for(int i = 1; i <= V; ++i) {
        // 2.'최단 거리 테이블'을 초기화
        dist[i] = INF;
    }

    dijkstra(K); // 시작 정점

	// 도착 정점까지의 최단 거리 출력
    cout << "The Shortest Distance : " << dist[M];
    return 0;
}

추가 : 최단 거리 경로 역추적(백트래킹)

시작 정점으로부터 도착 정점까지 최단 거리로 왔을 때 어떤 정점들을 거쳐서 최단 거리로 왔는지 경로 역추적이 필요합니다.

위 코드에서 약간의 코드가 추가될 것입니다.

1. 정점의 개수 + 1만큼의 백트래킹 배열을 하나 생성합니다.

2. 최단 거리를 업데이트할 때 해당 정점이 어느 정점에서 왔는지 백트래킹 배열에 기록합니다.

3. 기록 후, 경로를 저장할 배열을 하나 생성합니다.

4. 도착 정점을 알기 때문에 먼저 도착 정점을 경로를 저장할 배열에 넣어줍니다.

5. while 문내에서 정점이 0이 되기 전까지 백트래킹 배열을 탐색하며 경로를 저장할 배열에 경로를 넣어줍니다.

6. 경로를 도착지부터 넣었으므로 reverse 함수를 통해 경로를 저장할 배열을 뒤집습니다.

아래 주석과 함께 코드를 첨부하였습니다.

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9 // 최댓값

int V; // 정점의 개수
int E; // 간선의 개수
int K; // 시작 정점
int M; // 도착 정점
vector<int> dist; // 최단 거리 테이블
vector<pair<int, int>> graph[20001]; // 연결 정점, 최소 거리

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 최소힙,  {최소거리, 정점} 적은 가중치가 맨 앞에 오도록 함
vector<int> backtracking; // 1. 정점의 개수 + 1만큼의 백트래킹 배열을 하나 생성합니다.

void dijkstra(int cur) {
    pq.push({0, cur});
    dist[cur] = 0;
    while(!pq.empty()) {
        int cur_node = pq.top().second; // 현재 정점
        int cur_dist = pq.top().first; // 현재 가중치
        pq.pop();
        for(pair<int, int> element : graph[cur_node]) {
            int next_node = element.first;
            int next_distance = element.second + cur_dist;
            if(next_distance < dist[next_node]) {
                dist[next_node] = next_distance;
                backtracking[next_node] = cur_node; // 2. 최단 거리를 업데이트할 때 해당 정점이 어느 정점에서 왔는지 배열에 기록합니다.
                pq.push({next_distance, next_node});
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> V >> E; // 정점의 개수, 간선의 개수
    cin >> K >> M; // 시작 정점, 도착 정점
    dist.resize(V + 1);
    backtracking.resize(V + 1); // 경로 추적
    for(int i = 0; i < E; ++i) {
        int start, end, dist;
        cin >> start >> end >> dist;
        graph[start].emplace_back(make_pair(end, dist));
    }

    for(int i = 1; i <= V; ++i) {
        dist[i] = INF;
    }

    dijkstra(K); // 시작 정점

    cout << "The Shortest Distance : " << dist[M] << '\n';
    // 경로 추적 시작
    vector<int> path; // 3. 기록 후, 경로를 저장할 배열을 하나 생성합니다.
    path.emplace_back(M); // 4. 도착 정점을 알기 때문에 먼저 도착 정점을 경로를 저장할 배열에 넣어줍니다.
    int trace = backtracking[M];
    while(true) {
        // 5. while 문내에서 정점이 0이 되기 전까지 백트래킹 배열을 탐색하며 경로를 저장할 배열에 경로를 넣어줍니다.
        if(trace == 0) break;
        path.emplace_back(trace);
        trace = backtracking[trace];
    }
    // 6. 경로를 도착지부터 넣었으므로 reverse 함수를 통해 경로를 저장할 배열을 뒤집습니다.
    reverse(path.begin(), path.end());
    // 경로 출력
    for(int element : path) {
        cout << element << ' ';
    }

    return 0;
}