단순한 정리와 활용을 원하시는 분은 마지막 코드를 참조해주세요.
주석만으로도 충분히 이해하실 수 있습니다.
이번에는 최단 경로 알고리즘에 대해 알아보겠습니다.
알고리즘은 다음과 같이 문제를 정의합니다.
1) 문제 정의
1-1) 저점 u와 v 사이에 간선이 존재한다.
1-2) u와 v 사이에 여러 개의 경로가 존재한다면, 가장 빠른 경로는 무엇일까?
알고리즘은 다음과 같은 가정을 포함합니다.
2) 가정
2-1) 경로의 길이는 경로를 구성하는 간선들의 비용(길이, 가중치)합으로 정의된다.
-> edge의 수가 아닙니다.
2-2) 방향성 그래프를 가정합니다. 즉, 양방향 경로인 간선만 사용할 수 있습니다.
2-3) 모든 edge의 비용은 0 보다 큽니다.
-> 0을 자기자신으로 가는 경로의 비용으로 설정합니다.
-----------------------------------Dijkstra------------------------------------
출발점이 하나인 단일 출발점 문제에서 최단 경로를 찾는 방법에 대해 알아보겠습니다.
단일 출발점 문제는 하나의 정점에서 그래프 내의 다른 모든 정점으로 가는 최단 경로를 검색합니다.
1. 단일 출발점 문제
단일 출발점 문제는 다음과 같은 상황을 정의합니다.
1) 방향성 그래프
2) 모든 가중치는 0보다 큼
3) 출발 정점은 단 하나
단일 출발 정점 v에서 그래프에 속한 모든 정점으로 가는 최단 경로를 구하는 문제입니다.
2. 문제 해결 알고리즘 기본 개념
1) 변수 정의
1-1) S: 최단 경로를 발견한 정점 (vertex)들의 집합 (출발 정점 v 포함)
1-2) distance[w] (w는 집합 S에 포함되지 않는 vertex.): v에서 시작해서 S에 포함된 정점만 경유하여 w까지 가는 최단 경로의 길이
2) 최단 경로를 찾는 과정
2-1) S의 초기값은 {v}, distance[w]의 초기값은 출발 정점 v에서 그래프 내의 정점 w로 가는 간선의 가중치 입니다.
2-2) S에 없는 정점 중에서 최소 distance[u]를 갖는 정점 u를 선택합니다.
2-3) u는 S의 원소가 됩니다.
S에 원소가 추가되면, S에 포함되지 않는 정점 w의 distance[w]가 변경될 수 있습니다.
-> w의 distance는 항상 출발 정점 u에서 S에 포함된 정점을 경유하여 w로 도착하는 최단 거리로 갱신됩니다.
따라서 distance[w]는 min(distance[w], distance[u] + length or cost(<u, w>))으로 갱신됩니다.
즉, (본래 정점 w의 가중치) vs. (새로운 정점 u의 가중치 + u와 w를 잇는 간선의 가중치) 입니다.
이와 같은 문제는 Dijkstra의 알고리즘을 사용하여 해결합니다.
시작 정점부터 특정 정점까지 가는 경로의 최단 경로를 구하는 문제입니다.
항상 그래프 내의 정점을 경유해서 가는게 빠르니?
아니면, 시작 정점에서 직통으로 가는게 빠르니?
위 질문에 대한 답이 단일 출발점 문제의 답입니다.
3. Dijkstra의 알고리즘
알고리즘은 다음과 같이 구성됩니다.
1) 0에서 n-1까지 n개의 vertex가 존재합니다.
2) 출발점 v에서 나머지 모든 vertex까지 가는 가장 짧은 경로의 길이를 distance 배열에 저장하는 것이 목표입니다.
3) 출발점으로부터 최소 경로가 확정된 정점들의 집합 S는 found[n]에 저장됩니다.
-> i가 S에 포함되지 않을 때 found[i] = FALSE 입니다.
-> i가 S에 포함될 때 found[i] = TRUE 입니다.
4) 인접 행렬 cost[n][n]을 이용하여 그래프 G를 표현합니다.
-> cost[i][j]는 <i, j>의 비용입니다. (<i, j> = 정점 i와 j를 잇는 간선)
3-1. Dijkstra 알고리즘 구현
기울임 된 내용은 제가 공부할 때 이해를 위해 작성한 것 입니다.
1) choose() 알고리즘
모든 정점에 대해 S에 포함되지 않으면서 (최단 경로가 발견되지 않았고) 시작 정점과의 거리가 최소인 정점을 찾아 반환합니다.
모든 vertex에 대해 distance[i]가 최솟값 보다 작고, 해당 vertex가 아직 S에 포함되어 있지 않을 때
(min 초기값이 뭐지... = int 자료형의 최댓 값 --> 연결되지 않는 노드는 무한대이니까 제외 하려고 한건가 보다)
해당 vertex를 찾아 반환한다. (S에 포함되지 않은 모든 vertex에 대해 distance가 가장 작은 vertext를 반환)
2) shortestpath() 알고리즘
모든 정점 데이터에 대해 found를 FALSE로 초기화하고 distance는 시작 정점 v에서 각각의 정점으로 가는 간선의 비용으로 초기화 합니다.
이후 최단 경로가 발견되지 않은 정점 중 distance가 가장 작은 정점을 반환합니다
해당 정점을 최단 경로를 찾았다고 갱신합니다..
그래프 내에 새롭게 추가된 정점을 기준으로 그래프의 모든 정점들의 distance를 갱신 합니다.
모든 found를 FALSE로 초기화하고, distance는 기준 vertex v에서 각 vertex로 가는 경로의 비용으로 초기화 한다.
u는 choose 함수를 통해 반환된 값이고, found[u]는 TRUE로 갱신된다.
다시 모든 vertex w에 대해서 found[w]가 FALSE 일 때
distance[u] + cost[u][w]와 distance[w]의 크기를 비교하고,
distance[w]의 크기가 더 클 때, distance[w]의 크기를 distance[u] + cost[u][w]로 갱신해 줍니다.
-----------------------------------Floyd------------------------------------
다음 문제를 예시로 Floyd 알고리즘에 대해 설명드리겠습니다.
1. 모든 쌍들간의 최단 경로
해당 문제는 다음과 같이 정의됩니다.
"그래프 G에 포함된 모든 vertex의 쌍들에 대해 최단 경로를 찾는다."
해법은 다음과 같이 두가지 존재합니다.
1) V(G)에 속하는 모든 vertex에 대해 Dijkstra 알고리즘을 수행: 복잡도 = O(n^3)
2) 동적 프로그래밍 방법 (Dynamic programming method): 복잡도 = O(n^3) (with smaller constant factor)
-> 이게 Floyd 알고리즘
2. 동적 프로그래밍 알고리즘 (Floyd 알고리즘)
단일 출발점 문제를 해결하는 알고리즘과 달리
Floyd의 최단 경로 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아줍니다.
가정: 0에서 n-1까지 n개의 vertex가 존재
2-1 기본적인 자료구조
1) A(k)[i][j]: 0~k에 포함되는 정점들을 이용하여 구한 정점 i와 j를 잇는 경로의 최단 거리
2) 정점이 0 ~ n-1까지, 즉, n개 있을 때 우리가 원하는 답은 A(n-1)[i][j] 입니다.
3) A(-1), A(0), A(1), ...., A(n-1) 순으로 최단 거리를 구합니다.
*A(-1)은 모든 정점들의 쌍에 대한 초기값 입니다.
2-2 A^(k-1)을 이용하여 A^(k)를 생성하는 방법
1) vertex k를 지나지 않는 경로: A(k)[i][j] = A(k-1)[i][j] (어차피 k를 안 지나는 경로는 상관 없으니까)
2) vertex k를 지나는 경로
2-1) A(k)[i][j] = min( (A(k-1)[i][j]), (A(k-1)[i][k] + A(k-1)[k][j]) ), k>=0
2-2) A(-1)[i][j] = cost[i][j]
3. Floyd 알고리즘 구현
1) 모든 정점들에 대해 두 정점을 잇는 간선 정보를 A 행렬에 입력한다.
2) k를 기준으로 그래프 내의 모든 정점 i, j에 대한 가중치를 갱신한다.
EX)
0을 기준으로 시작 (k == 0)
그래프 내의 모든 정점 i와 j에 대하여
A[i][j]와 A[i][0] + A[0][j]의 대소를 비교한다.
즉, i에서 j까지 갈 때 기준 정점을 경유하는 것과 직행 중 어떤 경로가 더 빠른지 비교하는 것입니다.
Dijkstra는 위와 같은 판단을 시작 정점만을 기준으로 실행했습니다. (-> 단일 출발점 문제)
---------------------------Dijkstra & Floyd code----------------------------
1. Dijkstra 알고리즘
해당 알고리즘은 단일 출발점 문제의 해를 구합니다.
즉, 하나의 출발점으로부터 그래프 내의 모든 정점에 대한 최단 경로를 구합니다.
choose
모든 정점 중에서 아직 시작 정점과의 최단 거리가 결정되지 않고, 시작 정점 (출발점)과의 거리가 가장 짧은 정점을 반환합니다.
Shortest_Path_Dijkstra
choose에서 반환된 정점을 최단 거리가 결정되었다고 갱신합니다.
해당 정점을 기준으로 모든 정점에 대해 시작 정점과의 거리를 갱신합니다.
-> 반환된 정점을 경유하는게 빠른지 아닌지
int choose(int distance[], int n, int found[]) {
int min;
int min_pos;
min = INT_MAX;
min_pos = -1;
for (int i = 0; i < n; i++) {
if (distance[i] < min && found[i] == FALSE) {
min = distance[i];
min_pos = i;
}
}
return min_pos;
}
void Shortest_Path_Dijkstra(int start, int n) {
// Dijkstra 알고리즘으로 최단 경로를 구한다.
// 시작 정점으로부터 그래프 내의 모든 정점에 대한 최단 경로를 구합니다.
for (int i = 0; i < n; i++) {
distance[i] = weight[start][i]; // 시작 정점에서 다른 정점으로 향하는 가중치를 기준으로 초기화합니다.
found[i] = FALSE;
}
found[start] = TRUE; // 시작점은 그래프에 추가되었다고 가정하기 때문에
// 시작점의 방문 여부를 갱신해줍니다.
for (int i = 0; i < n - 1; i++) {
int u = choose(distance, n, found);
// 최단 거리가 결정되지 않고, 시작 정점과의 거리가 가장 짧은 정점을 반환합니다.
found[u] = TRUE; // 해당 정점의 최단 경로를 발견했다고 갱신합니다..
printf("%d is added to the Graph\n\n", u);
for (int j = 0; j < n; j++) {
if (found[j] == FALSE) { // 최단 경로를 발견하지 못 한 정점에 대해
if (distance[u] + weight[u][j] < distance[j]) {
// 시작 정점에서 j로 바로 가는게 빠를지, u를 경유해서 가는게 빠를지 판단 합니다.
printf("Before_distance update via[%d]: distance[%d] = %d\n", u, j, distance[j]);
distance[j] = distance[u] + weight[u][j];
printf("After_distance update via[%d]: distance[%d] = %d\n\n", u, j, distance[j]);
}
}
}
}
}
2. Floyd 알고리즘
모든 정점에 대해 각 정점 간의 최단 경로를 찾습니다.
아래 주석을 확인해주시면 되겠습니다.
void Shortest_Path_Floyd(void) {
// Floyd 알고리즘으로 최단 경로를 구한다.
// 해당 알고리즘은 모든 정점간의 최다 경로를 구합니다.
for (int u = 0; u < MAX_VERTICES; u++) {
for (int v = 0; v < MAX_VERTICES; v++) {
d[u][v] = weight[u][v];
}
}
for (int m = 0; m < MAX_VERTICES; m++) { // m이 경유하는 기준 정점이 됩니다.
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
if (d[i][j] > d[i][m] + d[m][j]) {
// 모든 정점 i와 j에 대해
// i에서 j로 바로 가는게 빠를지, m을 경유해서 가는게 빠를지 판단합니다.
// m을 경유해서 가는게 빠르다면,
// d[i][j] 갱신 후의 의미는 i->m->j를 내포합니다.
printf("Before_distance update via[%d]: distance[%d][%d] = %d\n", m, i, j, d[i][j]);
d[i][j] = d[i][m] + d[m][j];
printf("After_distance update via[%d]: distance[%d][%d] = %d\n\n", m, i, j, d[i][j]);
}
}
}
}
}
3. 전체 코드
// main.c
// Graph_Shortest_Path_Daijkstra_And_Floyd
//
// Created by 김경민 on 2020/04/20.
// Copyright © 2020 김경민. All rights reserved.
//
// 최단 경로 탐색 알고리즘을 구현한다.
// choose 함수에 우선 순위 큐를 사용하면 효율을 높일 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define INT_MAX 2147483647 // 최대 정수
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 7 // 정점의 수
#define INF 1000 // 무한대 (연결이 없는 경우)
int weight[MAX_VERTICES][MAX_VERTICES] = {
{0,7,INF,INF,3,10,INF},
{7,0,4,10,2,6,INF},
{INF,4,0,2,INF,INF,INF},
{INF,10,2,0,11,9,4},
{3,2,INF,11,0,INF,5},
{10,6,INF,9,INF,0,INF},
{INF,INF,INF,4,5,INF,0}
};
//int weight[MAX_VERTICES][MAX_VERTICES] = {
// {0,1,8,INF},
// {1,0,7,2},
// {8,7,0,3},
// {INF,2,3,0}
//};
/* Dijkstra 변수*/
int distance[MAX_VERTICES];
int found[MAX_VERTICES];
/* Floyd 변수*/
int d[MAX_VERTICES][MAX_VERTICES];
int choose(int distance[], int n, int found[]) {
int min;
int min_pos;
min = INT_MAX;
min_pos = -1;
for (int i = 0; i < n; i++) {
if (distance[i] < min && found[i] == FALSE) {
min = distance[i];
min_pos = i;
}
}
return min_pos;
}
void Shortest_Path_Dijkstra(int start, int n) {
// Dijkstra 알고리즘으로 최단 경로를 구한다.
// 시작 정점으로부터 그래프 내의 모든 정점에 대한 최단 경로를 구합니다.
for (int i = 0; i < n; i++) {
distance[i] = weight[start][i]; // 시작 정점에서 다른 정점으로 향하는 가중치를 기준으로 초기화합니다.
found[i] = FALSE;
}
found[start] = TRUE;
for (int i = 0; i < n - 1; i++) {
int u = choose(distance, n, found);
// 최단 경로가 발견되지 않고, 시작 정점과의 거리가 가장 짧은 정점을 반환합니다.
found[u] = TRUE; // 해당 정점을 그래프에 포합합니다.
printf("%d is added to the Graph\n\n", u);
for (int j = 0; j < n; j++) {
if (found[j] == FALSE) {
if (distance[u] + weight[u][j] < distance[j]) {
// 시작 정점에서 j로 바로 가는게 빠를지, u를 경유해서 가는게 빠를지 판단 합니다.
printf("Before_distance update via[%d]: distance[%d] = %d\n", u, j, distance[j]);
distance[j] = distance[u] + weight[u][j];
printf("After_distance update via[%d]: distance[%d] = %d\n\n", u, j, distance[j]);
}
}
}
}
}
void Shortest_Path_Floyd(void) {
// Floyd 알고리즘으로 최단 경로를 구한다.
// 해당 알고리즘은 모든 정점간의 최다 경로를 구합니다.
for (int u = 0; u < MAX_VERTICES; u++) {
for (int v = 0; v < MAX_VERTICES; v++) {
d[u][v] = weight[u][v];
}
}
for (int m = 0; m < MAX_VERTICES; m++) { // m이 경유하는 기준 정점이 됩니다.
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
if (d[i][j] > d[i][m] + d[m][j]) {
// 모든 정점 i와 j에 대해
// i에서 j로 바로 가는게 빠를지, m을 경유해서 가는게 빠를지 판단합니다.
// m을 경유해서 가는게 빠르다면,
// d[i][j] 갱신 후의 의미는 i->m->j를 내포합니다.
printf("Before_distance update via[%d]: distance[%d][%d] = %d\n", m, i, j, d[i][j]);
d[i][j] = d[i][m] + d[m][j];
printf("After_distance update via[%d]: distance[%d][%d] = %d\n\n", m, i, j, d[i][j]);
}
}
}
}
}
int main(void) {
/* Dijkstra */
#if 0
Shortes_tPath_Dijkstra(0, MAX_VERTICES);
#endif
/* Floyd*/
#if 1
Shortest_Path_Floyd();
#endif
printf("\n");
return 0;
}
4. 실행 결과
1) Dijkstra
2) Floyd
그래프의 모든 정점 쌍에 대한 최단 경로를 구하기 때문에
출력 갯수가 많습니다. (n * n)
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] 부록 - 1: 최소비용 신장트리 MST_Kruskal 알고리즘 (0) | 2020.05.13 |
|---|---|
| [자료구조 C 언어] C 프로그래밍 자료구조 - 19 : 네트워크 (AOV, AOE, EST, LST, critical path) (0) | 2020.03.19 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 17 : 그래프(3) 최소 신장 트리 (MST): Kruskal, Prim 알고리즘 (0) | 2020.03.19 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 16 : 그래프(2) 기초 연산: 깊이 우선 탐색, 넓이 우선 탐색 등 (0) | 2020.03.19 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 15 : 그래프(1) 기본 개념 (0) | 2020.03.18 |