14_shortest_path.cpp

Download
cpp 372 lines 10.5 KB 
  1/*
  2 * ์ตœ๋‹จ ๊ฒฝ๋กœ (Shortest Path)
  3 * Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS
  4 *
  5 * ๊ทธ๋ž˜ํ”„์—์„œ ์ •์  ๊ฐ„ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <queue>
 11#include <climits>
 12#include <algorithm>
 13
 14using namespace std;
 15
 16const int INF = INT_MAX;
 17
 18// =============================================================================
 19// 1. Dijkstra ์•Œ๊ณ ๋ฆฌ์ฆ˜
 20// =============================================================================
 21
 22vector<int> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int start) {
 23    vector<int> dist(n, INF);
 24    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
 25
 26    dist[start] = 0;
 27    pq.push({0, start});
 28
 29    while (!pq.empty()) {
 30        auto [d, u] = pq.top();
 31        pq.pop();
 32
 33        if (d > dist[u]) continue;
 34
 35        for (auto [v, w] : adj[u]) {
 36            if (dist[u] + w < dist[v]) {
 37                dist[v] = dist[u] + w;
 38                pq.push({dist[v], v});
 39            }
 40        }
 41    }
 42
 43    return dist;
 44}
 45
 46// ๊ฒฝ๋กœ ๋ณต์›
 47pair<vector<int>, vector<int>> dijkstraWithPath(int n, const vector<vector<pair<int, int>>>& adj, int start) {
 48    vector<int> dist(n, INF);
 49    vector<int> parent(n, -1);
 50    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
 51
 52    dist[start] = 0;
 53    pq.push({0, start});
 54
 55    while (!pq.empty()) {
 56        auto [d, u] = pq.top();
 57        pq.pop();
 58
 59        if (d > dist[u]) continue;
 60
 61        for (auto [v, w] : adj[u]) {
 62            if (dist[u] + w < dist[v]) {
 63                dist[v] = dist[u] + w;
 64                parent[v] = u;
 65                pq.push({dist[v], v});
 66            }
 67        }
 68    }
 69
 70    return {dist, parent};
 71}
 72
 73vector<int> reconstructPath(int start, int end, const vector<int>& parent) {
 74    vector<int> path;
 75    for (int at = end; at != -1; at = parent[at]) {
 76        path.push_back(at);
 77    }
 78    reverse(path.begin(), path.end());
 79
 80    if (path[0] != start) {
 81        return {};  // ๊ฒฝ๋กœ ์—†์Œ
 82    }
 83
 84    return path;
 85}
 86
 87// =============================================================================
 88// 2. Bellman-Ford ์•Œ๊ณ ๋ฆฌ์ฆ˜
 89// =============================================================================
 90
 91struct Edge {
 92    int from, to, weight;
 93};
 94
 95pair<vector<int>, bool> bellmanFord(int n, const vector<Edge>& edges, int start) {
 96    vector<int> dist(n, INF);
 97    dist[start] = 0;
 98
 99    // n-1๋ฒˆ relaxation
100    for (int i = 0; i < n - 1; i++) {
101        bool updated = false;
102        for (const auto& e : edges) {
103            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
104                dist[e.to] = dist[e.from] + e.weight;
105                updated = true;
106            }
107        }
108        if (!updated) break;  // ์กฐ๊ธฐ ์ข…๋ฃŒ
109    }
110
111    // ์Œ์ˆ˜ ์‚ฌ์ดํด ๊ฒ€์‚ฌ
112    for (const auto& e : edges) {
113        if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
114            return {dist, true};  // ์Œ์ˆ˜ ์‚ฌ์ดํด ์กด์žฌ
115        }
116    }
117
118    return {dist, false};
119}
120
121// =============================================================================
122// 3. Floyd-Warshall ์•Œ๊ณ ๋ฆฌ์ฆ˜
123// =============================================================================
124
125vector<vector<int>> floydWarshall(int n, vector<vector<int>>& dist) {
126    // dist๋Š” ์ดˆ๊ธฐ ์ธ์ ‘ ํ–‰๋ ฌ (์—ฐ๊ฒฐ ์—†์œผ๋ฉด INF)
127
128    for (int k = 0; k < n; k++) {
129        for (int i = 0; i < n; i++) {
130            for (int j = 0; j < n; j++) {
131                if (dist[i][k] != INF && dist[k][j] != INF) {
132                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
133                }
134            }
135        }
136    }
137
138    return dist;
139}
140
141// ๊ฒฝ๋กœ ๋ณต์› ๊ฐ€๋Šฅํ•œ ๋ฒ„์ „
142pair<vector<vector<int>>, vector<vector<int>>> floydWarshallWithPath(int n, vector<vector<int>>& dist) {
143    vector<vector<int>> next(n, vector<int>(n, -1));
144
145    // ์ดˆ๊ธฐํ™”: ์ง์ ‘ ์—ฐ๊ฒฐ๋œ ๊ฒฝ์šฐ
146    for (int i = 0; i < n; i++) {
147        for (int j = 0; j < n; j++) {
148            if (i != j && dist[i][j] != INF) {
149                next[i][j] = j;
150            }
151        }
152    }
153
154    for (int k = 0; k < n; k++) {
155        for (int i = 0; i < n; i++) {
156            for (int j = 0; j < n; j++) {
157                if (dist[i][k] != INF && dist[k][j] != INF &&
158                    dist[i][k] + dist[k][j] < dist[i][j]) {
159                    dist[i][j] = dist[i][k] + dist[k][j];
160                    next[i][j] = next[i][k];
161                }
162            }
163        }
164    }
165
166    return {dist, next};
167}
168
169// =============================================================================
170// 4. 0-1 BFS
171// =============================================================================
172
173vector<int> bfs01(int n, const vector<vector<pair<int, int>>>& adj, int start) {
174    vector<int> dist(n, INF);
175    deque<int> dq;
176
177    dist[start] = 0;
178    dq.push_front(start);
179
180    while (!dq.empty()) {
181        int u = dq.front();
182        dq.pop_front();
183
184        for (auto [v, w] : adj[u]) {
185            if (dist[u] + w < dist[v]) {
186                dist[v] = dist[u] + w;
187                if (w == 0) {
188                    dq.push_front(v);
189                } else {
190                    dq.push_back(v);
191                }
192            }
193        }
194    }
195
196    return dist;
197}
198
199// =============================================================================
200// 5. SPFA (Shortest Path Faster Algorithm)
201// =============================================================================
202
203pair<vector<int>, bool> spfa(int n, const vector<vector<pair<int, int>>>& adj, int start) {
204    vector<int> dist(n, INF);
205    vector<bool> inQueue(n, false);
206    vector<int> cnt(n, 0);  // ํ์— ๋“ค์–ด๊ฐ„ ํšŸ์ˆ˜
207    queue<int> q;
208
209    dist[start] = 0;
210    q.push(start);
211    inQueue[start] = true;
212    cnt[start] = 1;
213
214    while (!q.empty()) {
215        int u = q.front();
216        q.pop();
217        inQueue[u] = false;
218
219        for (auto [v, w] : adj[u]) {
220            if (dist[u] + w < dist[v]) {
221                dist[v] = dist[u] + w;
222                if (!inQueue[v]) {
223                    q.push(v);
224                    inQueue[v] = true;
225                    cnt[v]++;
226
227                    if (cnt[v] >= n) {
228                        return {dist, true};  // ์Œ์ˆ˜ ์‚ฌ์ดํด
229                    }
230                }
231            }
232        }
233    }
234
235    return {dist, false};
236}
237
238// =============================================================================
239// 6. K๋ฒˆ์งธ ์ตœ๋‹จ ๊ฒฝ๋กœ
240// =============================================================================
241
242vector<int> kthShortestPath(int n, const vector<vector<pair<int, int>>>& adj,
243                            int start, int end, int k) {
244    vector<int> kthDist;
245    vector<int> count(n, 0);
246    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
247
248    pq.push({0, start});
249
250    while (!pq.empty() && count[end] < k) {
251        auto [d, u] = pq.top();
252        pq.pop();
253
254        count[u]++;
255
256        if (u == end) {
257            kthDist.push_back(d);
258        }
259
260        if (count[u] <= k) {
261            for (auto [v, w] : adj[u]) {
262                pq.push({d + w, v});
263            }
264        }
265    }
266
267    return kthDist;
268}
269
270// =============================================================================
271// ํ…Œ์ŠคํŠธ
272// =============================================================================
273
274void printVector(const vector<int>& v) {
275    cout << "[";
276    for (size_t i = 0; i < v.size(); i++) {
277        if (v[i] == INF) cout << "โˆž";
278        else cout << v[i];
279        if (i < v.size() - 1) cout << ", ";
280    }
281    cout << "]";
282}
283
284int main() {
285    cout << "============================================================" << endl;
286    cout << "์ตœ๋‹จ ๊ฒฝ๋กœ ์˜ˆ์ œ" << endl;
287    cout << "============================================================" << endl;
288
289    // ํ…Œ์ŠคํŠธ ๊ทธ๋ž˜ํ”„
290    int n = 5;
291    vector<vector<pair<int, int>>> adj(n);
292    adj[0] = {{1, 4}, {2, 1}};
293    adj[1] = {{3, 1}};
294    adj[2] = {{1, 2}, {3, 5}};
295    adj[3] = {{4, 3}};
296
297    // 1. Dijkstra
298    cout << "\n[1] Dijkstra ์•Œ๊ณ ๋ฆฌ์ฆ˜" << endl;
299    auto dijkDist = dijkstra(n, adj, 0);
300    cout << "    0์—์„œ ๊ฐ ์ •์ ๊นŒ์ง€ ๊ฑฐ๋ฆฌ: ";
301    printVector(dijkDist);
302    cout << endl;
303
304    // ๊ฒฝ๋กœ ๋ณต์›
305    auto [dist, parent] = dijkstraWithPath(n, adj, 0);
306    auto path = reconstructPath(0, 4, parent);
307    cout << "    0 โ†’ 4 ๊ฒฝ๋กœ: ";
308    printVector(path);
309    cout << " (๊ฑฐ๋ฆฌ: " << dist[4] << ")" << endl;
310
311    // 2. Bellman-Ford
312    cout << "\n[2] Bellman-Ford ์•Œ๊ณ ๋ฆฌ์ฆ˜" << endl;
313    vector<Edge> edges = {
314        {0, 1, 4}, {0, 2, 1}, {1, 3, 1}, {2, 1, 2}, {2, 3, 5}, {3, 4, 3}
315    };
316    auto [bfDist, hasNegCycle] = bellmanFord(n, edges, 0);
317    cout << "    0์—์„œ ๊ฐ ์ •์ ๊นŒ์ง€ ๊ฑฐ๋ฆฌ: ";
318    printVector(bfDist);
319    cout << endl;
320    cout << "    ์Œ์ˆ˜ ์‚ฌ์ดํด: " << (hasNegCycle ? "์žˆ์Œ" : "์—†์Œ") << endl;
321
322    // 3. Floyd-Warshall
323    cout << "\n[3] Floyd-Warshall ์•Œ๊ณ ๋ฆฌ์ฆ˜" << endl;
324    vector<vector<int>> distMatrix(4, vector<int>(4, INF));
325    for (int i = 0; i < 4; i++) distMatrix[i][i] = 0;
326    distMatrix[0][1] = 3;
327    distMatrix[0][2] = 8;
328    distMatrix[1][2] = 2;
329    distMatrix[2][3] = 1;
330    distMatrix[0][3] = 7;
331
332    floydWarshall(4, distMatrix);
333    cout << "    ๋ชจ๋“  ์Œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ:" << endl;
334    for (int i = 0; i < 4; i++) {
335        cout << "      " << i << ": ";
336        printVector(distMatrix[i]);
337        cout << endl;
338    }
339
340    // 4. 0-1 BFS
341    cout << "\n[4] 0-1 BFS" << endl;
342    vector<vector<pair<int, int>>> adj01(4);
343    adj01[0] = {{1, 0}, {2, 1}};
344    adj01[1] = {{2, 0}, {3, 1}};
345    adj01[2] = {{3, 0}};
346    auto dist01 = bfs01(4, adj01, 0);
347    cout << "    0์—์„œ ๊ฐ ์ •์ ๊นŒ์ง€ ๊ฑฐ๋ฆฌ (0-1): ";
348    printVector(dist01);
349    cout << endl;
350
351    // 5. K๋ฒˆ์งธ ์ตœ๋‹จ ๊ฒฝ๋กœ
352    cout << "\n[5] K๋ฒˆ์งธ ์ตœ๋‹จ ๊ฒฝ๋กœ" << endl;
353    auto kthDists = kthShortestPath(n, adj, 0, 4, 3);
354    cout << "    0 โ†’ 4 ์˜ 1~3๋ฒˆ์งธ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ: ";
355    printVector(kthDists);
356    cout << endl;
357
358    // 6. ๋ณต์žก๋„ ์š”์•ฝ
359    cout << "\n[6] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
360    cout << "    | ์•Œ๊ณ ๋ฆฌ์ฆ˜         | ์‹œ๊ฐ„๋ณต์žก๋„       | ์Œ์ˆ˜ ๊ฐ€์ค‘์น˜ |" << endl;
361    cout << "    |------------------|------------------|-------------|" << endl;
362    cout << "    | Dijkstra         | O((V+E) log V)   | X           |" << endl;
363    cout << "    | Bellman-Ford     | O(VE)            | O (์‚ฌ์ดํดX) |" << endl;
364    cout << "    | Floyd-Warshall   | O(Vยณ)            | O (์‚ฌ์ดํดX) |" << endl;
365    cout << "    | 0-1 BFS          | O(V + E)         | 0,1๋งŒ       |" << endl;
366    cout << "    | SPFA             | O(VE) ํ‰๊ท  O(E)  | O (์‚ฌ์ดํดX) |" << endl;
367
368    cout << "\n============================================================" << endl;
369
370    return 0;
371}