1/*
2 * ์ต๋จ ๊ฒฝ๋ก (Shortest Path)
3 * Dijkstra, Bellman-Ford, Floyd-Warshall
4 *
5 * ๊ทธ๋ํ์์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์
๋๋ค.
6 */
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <limits.h>
11#include <stdbool.h>
12
13#define INF INT_MAX
14
15/* =============================================================================
16 * 1. ๊ทธ๋ํ ๊ตฌ์กฐ
17 * ============================================================================= */
18
19typedef struct Edge {
20 int dest;
21 int weight;
22 struct Edge* next;
23} Edge;
24
25typedef struct {
26 Edge** adj;
27 int vertices;
28} Graph;
29
30Graph* graph_create(int vertices) {
31 Graph* g = malloc(sizeof(Graph));
32 g->vertices = vertices;
33 g->adj = calloc(vertices, sizeof(Edge*));
34 return g;
35}
36
37void graph_add_edge(Graph* g, int src, int dest, int weight) {
38 Edge* edge = malloc(sizeof(Edge));
39 edge->dest = dest;
40 edge->weight = weight;
41 edge->next = g->adj[src];
42 g->adj[src] = edge;
43}
44
45void graph_free(Graph* g) {
46 for (int i = 0; i < g->vertices; i++) {
47 Edge* e = g->adj[i];
48 while (e) {
49 Edge* temp = e;
50 e = e->next;
51 free(temp);
52 }
53 }
54 free(g->adj);
55 free(g);
56}
57
58/* =============================================================================
59 * 2. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ (๋ฐฐ์ด ๊ธฐ๋ฐ)
60 * ============================================================================= */
61
62int* dijkstra_array(Graph* g, int src) {
63 int* dist = malloc(g->vertices * sizeof(int));
64 bool* visited = calloc(g->vertices, sizeof(bool));
65
66 for (int i = 0; i < g->vertices; i++)
67 dist[i] = INF;
68 dist[src] = 0;
69
70 for (int count = 0; count < g->vertices - 1; count++) {
71 /* ์ต์ ๊ฑฐ๋ฆฌ ์ ์ ์ฐพ๊ธฐ */
72 int min_dist = INF, u = -1;
73 for (int v = 0; v < g->vertices; v++) {
74 if (!visited[v] && dist[v] < min_dist) {
75 min_dist = dist[v];
76 u = v;
77 }
78 }
79
80 if (u == -1) break;
81 visited[u] = true;
82
83 /* ์ธ์ ์ ์ ๊ฐฑ์ */
84 Edge* e = g->adj[u];
85 while (e) {
86 if (!visited[e->dest] && dist[u] != INF &&
87 dist[u] + e->weight < dist[e->dest]) {
88 dist[e->dest] = dist[u] + e->weight;
89 }
90 e = e->next;
91 }
92 }
93
94 free(visited);
95 return dist;
96}
97
98/* =============================================================================
99 * 3. ๋ค์ต์คํธ๋ผ (์ฐ์ ์์ ํ)
100 * ============================================================================= */
101
102typedef struct {
103 int vertex;
104 int dist;
105} HeapNode;
106
107typedef struct {
108 HeapNode* data;
109 int size;
110 int capacity;
111} MinHeap;
112
113MinHeap* heap_create(int capacity) {
114 MinHeap* h = malloc(sizeof(MinHeap));
115 h->data = malloc(capacity * sizeof(HeapNode));
116 h->size = 0;
117 h->capacity = capacity;
118 return h;
119}
120
121void heap_push(MinHeap* h, int vertex, int dist) {
122 int i = h->size++;
123 h->data[i].vertex = vertex;
124 h->data[i].dist = dist;
125
126 while (i > 0) {
127 int parent = (i - 1) / 2;
128 if (h->data[parent].dist <= h->data[i].dist) break;
129 HeapNode temp = h->data[parent];
130 h->data[parent] = h->data[i];
131 h->data[i] = temp;
132 i = parent;
133 }
134}
135
136HeapNode heap_pop(MinHeap* h) {
137 HeapNode min = h->data[0];
138 h->data[0] = h->data[--h->size];
139
140 int i = 0;
141 while (2 * i + 1 < h->size) {
142 int smallest = i;
143 int left = 2 * i + 1;
144 int right = 2 * i + 2;
145
146 if (h->data[left].dist < h->data[smallest].dist)
147 smallest = left;
148 if (right < h->size && h->data[right].dist < h->data[smallest].dist)
149 smallest = right;
150
151 if (smallest == i) break;
152
153 HeapNode temp = h->data[i];
154 h->data[i] = h->data[smallest];
155 h->data[smallest] = temp;
156 i = smallest;
157 }
158
159 return min;
160}
161
162int* dijkstra_heap(Graph* g, int src) {
163 int* dist = malloc(g->vertices * sizeof(int));
164 for (int i = 0; i < g->vertices; i++)
165 dist[i] = INF;
166 dist[src] = 0;
167
168 MinHeap* pq = heap_create(g->vertices * g->vertices);
169 heap_push(pq, src, 0);
170
171 while (pq->size > 0) {
172 HeapNode node = heap_pop(pq);
173 int u = node.vertex;
174 int d = node.dist;
175
176 if (d > dist[u]) continue;
177
178 Edge* e = g->adj[u];
179 while (e) {
180 if (dist[u] + e->weight < dist[e->dest]) {
181 dist[e->dest] = dist[u] + e->weight;
182 heap_push(pq, e->dest, dist[e->dest]);
183 }
184 e = e->next;
185 }
186 }
187
188 free(pq->data);
189 free(pq);
190 return dist;
191}
192
193/* =============================================================================
194 * 4. ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ
195 * ============================================================================= */
196
197typedef struct {
198 int src;
199 int dest;
200 int weight;
201} EdgeList;
202
203int* bellman_ford(int vertices, EdgeList edges[], int num_edges, int src, bool* has_negative_cycle) {
204 int* dist = malloc(vertices * sizeof(int));
205 for (int i = 0; i < vertices; i++)
206 dist[i] = INF;
207 dist[src] = 0;
208
209 /* V-1๋ฒ ๋ฐ๋ณต */
210 for (int i = 0; i < vertices - 1; i++) {
211 for (int j = 0; j < num_edges; j++) {
212 int u = edges[j].src;
213 int v = edges[j].dest;
214 int w = edges[j].weight;
215
216 if (dist[u] != INF && dist[u] + w < dist[v])
217 dist[v] = dist[u] + w;
218 }
219 }
220
221 /* ์์ ์ฌ์ดํด ๊ฒ์ฌ */
222 *has_negative_cycle = false;
223 for (int j = 0; j < num_edges; j++) {
224 int u = edges[j].src;
225 int v = edges[j].dest;
226 int w = edges[j].weight;
227
228 if (dist[u] != INF && dist[u] + w < dist[v]) {
229 *has_negative_cycle = true;
230 break;
231 }
232 }
233
234 return dist;
235}
236
237/* =============================================================================
238 * 5. ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ์ฆ
239 * ============================================================================= */
240
241int** floyd_warshall(int** graph, int vertices) {
242 int** dist = malloc(vertices * sizeof(int*));
243 for (int i = 0; i < vertices; i++) {
244 dist[i] = malloc(vertices * sizeof(int));
245 for (int j = 0; j < vertices; j++)
246 dist[i][j] = graph[i][j];
247 }
248
249 for (int k = 0; k < vertices; k++) {
250 for (int i = 0; i < vertices; i++) {
251 for (int j = 0; j < vertices; j++) {
252 if (dist[i][k] != INF && dist[k][j] != INF &&
253 dist[i][k] + dist[k][j] < dist[i][j]) {
254 dist[i][j] = dist[i][k] + dist[k][j];
255 }
256 }
257 }
258 }
259
260 return dist;
261}
262
263/* =============================================================================
264 * 6. ๊ฒฝ๋ก ๋ณต์
265 * ============================================================================= */
266
267int* dijkstra_with_path(Graph* g, int src, int** parent) {
268 int* dist = malloc(g->vertices * sizeof(int));
269 *parent = malloc(g->vertices * sizeof(int));
270 bool* visited = calloc(g->vertices, sizeof(bool));
271
272 for (int i = 0; i < g->vertices; i++) {
273 dist[i] = INF;
274 (*parent)[i] = -1;
275 }
276 dist[src] = 0;
277
278 for (int count = 0; count < g->vertices - 1; count++) {
279 int min_dist = INF, u = -1;
280 for (int v = 0; v < g->vertices; v++) {
281 if (!visited[v] && dist[v] < min_dist) {
282 min_dist = dist[v];
283 u = v;
284 }
285 }
286
287 if (u == -1) break;
288 visited[u] = true;
289
290 Edge* e = g->adj[u];
291 while (e) {
292 if (!visited[e->dest] && dist[u] != INF &&
293 dist[u] + e->weight < dist[e->dest]) {
294 dist[e->dest] = dist[u] + e->weight;
295 (*parent)[e->dest] = u;
296 }
297 e = e->next;
298 }
299 }
300
301 free(visited);
302 return dist;
303}
304
305void print_path(int parent[], int dest) {
306 if (parent[dest] == -1) {
307 printf("%d", dest);
308 return;
309 }
310 print_path(parent, parent[dest]);
311 printf(" -> %d", dest);
312}
313
314/* =============================================================================
315 * ํ
์คํธ
316 * ============================================================================= */
317
318int main(void) {
319 printf("============================================================\n");
320 printf("์ต๋จ ๊ฒฝ๋ก (Shortest Path) ์์ \n");
321 printf("============================================================\n");
322
323 /* 1. ๋ค์ต์คํธ๋ผ (๋ฐฐ์ด) */
324 printf("\n[1] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ (๋ฐฐ์ด)\n");
325 Graph* g1 = graph_create(5);
326 graph_add_edge(g1, 0, 1, 4);
327 graph_add_edge(g1, 0, 2, 1);
328 graph_add_edge(g1, 2, 1, 2);
329 graph_add_edge(g1, 1, 3, 1);
330 graph_add_edge(g1, 2, 3, 5);
331 graph_add_edge(g1, 3, 4, 3);
332
333 int* dist1 = dijkstra_array(g1, 0);
334 printf(" 0์์ ๊ฐ ์ ์ ๊น์ง ๊ฑฐ๋ฆฌ:\n");
335 for (int i = 0; i < 5; i++)
336 printf(" 0 -> %d: %d\n", i, dist1[i]);
337 free(dist1);
338
339 /* 2. ๋ค์ต์คํธ๋ผ (ํ) */
340 printf("\n[2] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ (ํ)\n");
341 int* dist2 = dijkstra_heap(g1, 0);
342 printf(" 0์์ ๊ฐ ์ ์ ๊น์ง ๊ฑฐ๋ฆฌ:\n");
343 for (int i = 0; i < 5; i++)
344 printf(" 0 -> %d: %d\n", i, dist2[i]);
345 free(dist2);
346
347 /* 3. ๊ฒฝ๋ก ๋ณต์ */
348 printf("\n[3] ๊ฒฝ๋ก ๋ณต์\n");
349 int* parent;
350 int* dist3 = dijkstra_with_path(g1, 0, &parent);
351 for (int i = 1; i < 5; i++) {
352 printf(" 0 -> %d (๊ฑฐ๋ฆฌ %d): ", i, dist3[i]);
353 print_path(parent, i);
354 printf("\n");
355 }
356 free(dist3);
357 free(parent);
358 graph_free(g1);
359
360 /* 4. ๋ฒจ๋ง-ํฌ๋ */
361 printf("\n[4] ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ\n");
362 EdgeList edges[] = {
363 {0, 1, 4}, {0, 2, 1}, {2, 1, 2},
364 {1, 3, 1}, {2, 3, 5}, {3, 4, 3}
365 };
366 bool has_neg_cycle;
367 int* dist4 = bellman_ford(5, edges, 6, 0, &has_neg_cycle);
368 printf(" ์์ ์ฌ์ดํด: %s\n", has_neg_cycle ? "์์" : "์์");
369 printf(" ๊ฑฐ๋ฆฌ: ");
370 for (int i = 0; i < 5; i++)
371 printf("%d ", dist4[i]);
372 printf("\n");
373 free(dist4);
374
375 /* ์์ ์ฌ์ดํด ํ
์คํธ */
376 printf("\n ์์ ๊ฐ์ ํ
์คํธ:\n");
377 EdgeList edges_neg[] = {
378 {0, 1, 1}, {1, 2, -1}, {2, 0, -1}
379 };
380 int* dist_neg = bellman_ford(3, edges_neg, 3, 0, &has_neg_cycle);
381 printf(" ์์ ์ฌ์ดํด: %s\n", has_neg_cycle ? "์์" : "์์");
382 free(dist_neg);
383
384 /* 5. ํ๋ก์ด๋-์์
*/
385 printf("\n[5] ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ์ฆ\n");
386 int** matrix = malloc(4 * sizeof(int*));
387 for (int i = 0; i < 4; i++) {
388 matrix[i] = malloc(4 * sizeof(int));
389 for (int j = 0; j < 4; j++)
390 matrix[i][j] = (i == j) ? 0 : INF;
391 }
392 matrix[0][1] = 3;
393 matrix[0][3] = 7;
394 matrix[1][0] = 8;
395 matrix[1][2] = 2;
396 matrix[2][0] = 5;
397 matrix[2][3] = 1;
398 matrix[3][0] = 2;
399
400 int** dist5 = floyd_warshall(matrix, 4);
401 printf(" ๋ชจ๋ ์ ์ต๋จ ๊ฑฐ๋ฆฌ:\n");
402 printf(" ");
403 for (int i = 0; i < 4; i++) printf("%4d ", i);
404 printf("\n");
405 for (int i = 0; i < 4; i++) {
406 printf(" %d: ", i);
407 for (int j = 0; j < 4; j++) {
408 if (dist5[i][j] == INF)
409 printf(" INF ");
410 else
411 printf("%4d ", dist5[i][j]);
412 }
413 printf("\n");
414 }
415
416 for (int i = 0; i < 4; i++) {
417 free(matrix[i]);
418 free(dist5[i]);
419 }
420 free(matrix);
421 free(dist5);
422
423 /* 6. ์๊ณ ๋ฆฌ์ฆ ๋น๊ต */
424 printf("\n[6] ์๊ณ ๋ฆฌ์ฆ ๋น๊ต\n");
425 printf(" | ์๊ณ ๋ฆฌ์ฆ | ์๊ฐ๋ณต์ก๋ | ํน์ง |\n");
426 printf(" |---------------|---------------|-------------------|\n");
427 printf(" | ๋ค์ต์คํธ๋ผ(๋ฐฐ์ด)| O(Vยฒ) | ์์ ๊ฐ์ค์น๋ง |\n");
428 printf(" | ๋ค์ต์คํธ๋ผ(ํ) | O(E log V) | ํฌ์ ๊ทธ๋ํ ์ต์ |\n");
429 printf(" | ๋ฒจ๋ง-ํฌ๋ | O(V * E) | ์์ ๊ฐ์ค์น ํ์ฉ |\n");
430 printf(" | ํ๋ก์ด๋-์์
| O(Vยณ) | ๋ชจ๋ ์ ์ต๋จ๊ฒฝ๋ก |\n");
431
432 printf("\n============================================================\n");
433
434 return 0;
435}