최단 경로 문제는 네트워크에서 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 간선의 가중치는 비용, 거리, 시간 등을 나타낸다.
예를 들어 위 그래프에서 정점 0에서 점점 3으로 가는 최단 경로는 0,4,1,2,3 이고, 비용은 11이다. 다른 경로도 존재하지만 이 경로가 최단 거리이다. 사람은 특별한 과정 없이 바로 최단 경로를 도출할 수 있지만 이것을 어떻게 프로그램으로 만들 것인지가 관건이다.
최단 경로를 구할 수 있는 알고리즘은 Dijkstar 알고리즘과 Floyd 알고리즘이 대표적으로 있다. 다익스트라 알고리즘은 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다. 플로이드 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다. 가중치는 가중치 인점 행렬에 저장되어 있다고 가정하고, 직접적인 간선이 연결되어 있지 않다면 무한대값을 저장했다고 가정하자.
인접 행렬과 가중치 행렬의 차이점은 간선의 유무를 무한대로 해 두었다는 것이다. 가중치가 0인 경우도 존재할 수 있기 때문이다.
다익스트라 알고리즘은 네트워크에서 하나의 시작 정점으로부터 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 최단 경로는 경로의 길이 순으로 구해진다. 먼저 집합 S를 시작 정점 v로부터의 최단 경로가 이미 발견된 정점들의 집합이라고 하자. 다익스트라 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 distance 배열이 필요하다.
아래 단계들을 보면서 distance 배열이 어떻게 갱신되는지 확인해 보자.
기준 정점 0에서 가장 최단 거리는 정점 4이다. 그러면 정점 4를 경유하면 정점 0에서 목표 정점까지의 최단 거리를 알아낼 수 있으므로, 정점 4를 통해 갈 수 있는 경로값이 현재의 distance 값보다 더 작으면 갱신해준다. 따라서 Step1에서는 정점 1로 가는 거리가 7이었는데 5로 갱신된 것을 확인할 수 있다.
이 과정들을 반복해주면 된다.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 10000000
typedef struct GraphType {
int n;
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int distance[MAX_VERTICES];
int found[MAX_VERTICES];
// 방문하지 않은 정점 중에서 거리가 가장 짧은 인덱스 반환
int choose(int distance[], int n, int found[]) {
int i, min, minpos;
min = INT_MAX;
minpos = -1;
for(i = 0; i < n; i++)
if (distance[i] < min && !found[i]) {
min = distance[i];
minpos = i;
}
return minpos;
}
void print_status(GraphType* g) {
static int step = 1;
printf("STEP %d: ", step++);
printf("distance: ");
for (int i = 0; i < g->n; i++) {
if (distance[i] == INF)
printf(" * ");
else
printf("%2d ", distance[i]);
}
printf("\n");
printf(" found: ");
for (int i = 0; i < g->n; i++)
printf("%2d ", found[i]);
printf("\n\n");
}
void shortest_path(GraphType* g, int start) {
int i, u, w;
for (i = 0; i < g->n; i++) {
distance[i] = g->weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE;
distance[start] = 0;
for (i = 0; i < g->n - 1; i++) {
print_status(g);
u = choose(distance, g->n, found);
found[u] = TRUE;
for (w = 0; w < g->n; w++)
if (!found[w])
if (distance[u] + g->weight[u][w] < distance[w])
distance[w] = distance[u] + g->weight[u][w];
}
}
int main(void) {
GraphType g = { 7,
{{ 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 } }
};
shortest_path(&g, 0);
return 0;
}
그래프에 존재하는 모든 정점 사이의 최단 경로를 구하려면 다익스트라의 알고리즘을 정점의 수만큼 반복 실행하면 된다. 그러나 모든 정점 사이의 최단 거리를 구하려면 더 간단하고 좋은 알고리즘이 존재한다. 플로이드 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘이다.
플로이드 알고리즘은 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성되어 있다. 먼저 인접 행렬은 i == j라면 weight[i][j] = 0으로 하고 만약 두 개의 정점 i, j 사이에 간선이 존재하지 않으면 weight[i][j] == 라고 하자. 정점 i, j 사이에 간선이 존재하면 물론 weight[i][j]는 간선 (i, j)의 가중치가 된다. 플로이드 알고리즘은 삼중 반복문으로 표현된다.
1. 정점 k를 거쳐서 가지 않는 경우
: 는 k보다 큰 정점은 통과하지 않으므로 이경우 최단 거리는 가 된다.
2. 정점 k를 통과하는 경우
: 이 경우 i에서 k까지의 최단 거리 에다가 k에서 j까지의 최단 거리인 를 더한 값이 될 것이다.
다음은 플로이드 전체 과정을 단계별로 나타낸 것이다.
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000
typedef struct GraphType {
int n;
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int A[MAX_VERTICES][MAX_VERTICES];
void printA(GraphType* g) {
int i, j;
printf("=====================");
for (i = 0; i < g->n; i++) {
for (j = 0; j < g->n; j++) {
if (A[i][j] == INF)
printf(" * ");
else printf("%3d ", A[i][j]);
}
printf("\n");
}
printf("=====================");
}
void floyd(GraphType* g) {
int i, j, k;
for (i = 0; i < g->n; i++)
for (j = 0; j < g->n; j++)
A[i][j] = g->weight[i][j];
printA(g);
for (k = 0; k < g->n; k++) { // 경유할 정점
for (i = 0; i < g->n; i++) // 시작 정점
for (j = 0; j < g->n; j++) // 목표 정점
if (A[i][k] + A[k][j] < A[i][j])
A[i][j] = A[i][k] + A[k][j];
printA(g);
}
}
int main(void) {
GraphType g = { 7,
{{ 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 } }
};
floyd(&g);
return 0;
}
출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구
https://loosie.tistory.com/146?utm_source=chatgpt.com
https://roytravel.tistory.com/340?utm_source=chatgpt.com