#C++ #알고리즘 #자료구조

다익스트라 알고리즘

다익스트라 알고리즘에 대한 개념은 쉽게 많은 정보를 찾을 수 있으니 구현과 최단 거리가 아닌 최단 경로를 구하는 방법에 대해 알아보겠습니다.

다익스트라 요약

최단경로를 발견한 정점의 집합을 S라고 할때 다익스트라 알고리즘의 매 단계에서 집합 S에 있지 않은 정점중 가장 distance값이 가장 적은, 즉 가장 가까운 정점을 집합 S에 추가하고 그 다음, 다른 정점들의 distance값을 업데이트 합니다. 새로 가장 까운 정점으로 정점 u가 뽑혔다면 정점 u를 거쳐 다른 정점까지 가는 거리와 기존에 해당 정점까지의 거리를 비교해 거리가 더 가까운 값을 기준으로 업데이트 합니다.

아래의 식을 보면 더 쉽게 이해할 수 있습니다. 아래의 식은 위에서 설명한 것을 식으로 나타낸 것입니다.

1
distance[w] = min(distance[w], distance[u] + weight[u][w])

최단경로 추적 구현

다익스트라 알고리즘을 이용하면 최단 거리는 distance 배열에 저장되어 있어 쉽게 구할 수 있습니다. 하지만 거리가 아니라 최단 경로를 구하려 한다면, 시작 정점에서부터 해당 정점까지 지나온 경로를 기록해두어야 합니다.

아래의 C++로 구현한 코드를 보면 최단 경로가 업데이트 될 때마다 from 배열을 업데이트 하는 것을 볼 수 있습니다. from 배열은 해당 정점까지의 최단 거리가 업데이트 될때 해당 정점까지 의 거리를 업데이트시킨 바로 이전에 방문하게 되는 정점을 의미합니다. 예를 들어, from[5]는 정점 5까지의 최단 경로에서 정점 5 바로 이전에 방문하는 정점을 의미합니다.

따라서 도착지에서 출발지까지 역순으로 재귀함수를 이용해 출력하면 쉽게 최단 경로를 구할 수 있습니다. 경로 출력에 관한 함수는 trace_path()와 print_path()입니다.

쉽게 이해할 수 있도록 최대한 주석을 달아 두었으니 주석을 참고해주세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

class Graph {
public:
    int n;
    // 인접 정점
    // first: 정점, second: 가중치
    vector<pii>* adj;

    Graph(int n) {
        this->n = n;
        adj = new vector<pii>[n];
    }

    // 간선 추가
    void insertEdge(int u, int v, int w) {
        this->adj[u].push_back(make_pair(v, w));
        this->adj[v].push_back(make_pair(u, w));
    }
};

class Compare {
public:
    // 우선순위 큐를 위한 비교 함수
    bool operator() (pii a, pii b) {
        return a.second > b.second;
    }
};

vector<int>* dijkstra(Graph* g, int start) {
    // 최단 거리가 발견되면 true
    vector<bool> found(g->n, false);

    // 해당 정점까지의 거리 (default : 무한)
    vector<int> distance(g->n, INT_MAX);

    // 최단거리가 업데이트 될때 바로 이전에 방문하게 되는 정점  
    vector<int>* from = new vector<int>(g->n);

    // 가장 가까운 정점을 찾기 위한 우선순위 큐
    // first: 정점 번호, second: 정점까지의 거리
    priority_queue<pii, vector<pii>, Compare> pq;

    // 출발지의 최단거리 발견
    found[start] = true;
    // 출발지까지 거리 0
    distance[start] = 0;

    // 우선순위 큐에 넣는다.
    pq.push(make_pair(start, 0));

    //for (int i = 0; i < g->n; i++) {
    while(!pq.empty()) {
        // 가장 가까운 정점을 우선순위 큐에서 꺼낸다.
        int u = pq.top().first;
        pq.pop();

        // 최단거리 발견
        found[u] = true;
        for (int j = 0; j < g->adj[u].size(); j++) {
            // 정점 u의 인접정점의 최단거리 업데이트
            pii v = g->adj[u][j];

            if (!found[v.first]) {
                if (distance[u] + v.second < distance[v.first]) {
                    distance[v.first] = distance[u] + v.second;
                    (*from)[v.first] = u;

                    // 우선순위 큐에 추가
                    pq.push(make_pair(v.first, distance[v.first]));
                }
            }
        }
    }

    return from;
}

// from[n]에서 목적지까지의 정점을 재귀적으로 출력한다.  
void trace_path(int s, int e, vector<int>* from) {
    // 기저 조건 : 시작점과 목적지가 같은 경우  
    if ((*from)[e] == s) {
        cout << s << " -> ";
        return;
    
    }

    // 재귀호출을 통해 정점 e전의 정점에 대한 경로를 출력한다..  
    trace_path(s, (*from)[e], from);
    
    // 최단경로에서 정점 e 바로 이전의 정점를 화면에 출력한다.  
    cout << (*from)[e] << " - > ";
}

// 마지막 목적지를 간편하게 화면의 출력하기 위해 함수 분리  
void print_path(int s, int e, vector<int>* from) {
    // 위의 trace_path를 호출하여 최단 경로를 출력한후,  
    trace_path(s, e, from);

    // 목적지의 정점 번호도 출력한다.  
    cout << e;
}


int main(void) {
    Graph* g = new Graph(7);
    g->insertEdge(0, 1, 7);
    g->insertEdge(1, 0, 7);
    g->insertEdge(0, 4, 3);
    g->insertEdge(4, 0, 3);
    g->insertEdge(0, 5, 10);
    g->insertEdge(5, 0, 10);
    g->insertEdge(1, 4, 2);
    g->insertEdge(4, 1, 2);
    g->insertEdge(1, 5, 6);
    g->insertEdge(5, 1, 6);
    g->insertEdge(1, 2, 4);
    g->insertEdge(2, 1, 4);
    g->insertEdge(1, 3, 10);
    g->insertEdge(3, 1, 10);
    g->insertEdge(2, 3, 2);
    g->insertEdge(3, 2, 2);
    g->insertEdge(4, 3, 11);
    g->insertEdge(3, 4, 11);
    g->insertEdge(4, 6, 5);
    g->insertEdge(6, 4, 5);
    g->insertEdge(6, 3, 4);
    g->insertEdge(3, 6, 4);
    g->insertEdge(3, 5, 9);
    g->insertEdge(5, 3, 9);


    // 최단 경로를 구한다.
    auto from = dijkstra(g, 0);

    // 0부터 각 정점까지의 경로 출력
    for (int i = 0; i < g->n; i++) {
        cout << "0 -> " << i << " : ";
        print_path(0, i, from);
        cout << "\n";
    }

    return 0;
}

실행 결과

다익스트라 최단 경로

#C++ #알고리즘 #자료구조


Follow @techbless