예빈 ・ 2020. 3. 14. 19:07
다익스트라 알고리즘을 C언어로 구현했다!
먼저 distance배열에서 가중치가 제일 작은 노드를 골라 인덱스를 반환하는 choose함수를 만들었다.
다음은 최단 경로를 출력하는 함수!
거리가 무한대하면 간선이 연결되지 않은 것으로 간주하고 *를 출력하고, 아니라면 거리값을 출력.
또, 노드 인덱스를 방문했으면 1을, 방문하지 않았으면 0을 출력한다.
다음은 시작노드로부터의 최단 경로를 찾는 함수를 만들었다.
시작 정점부터 방문하여 배열값과 방문 여부를 표시한다.
다음 정점들 중 distance값이 가장 작은 정점을 고르고 방문 표시하는 과정이 계속된다.
메인 함수에서는 그래프g의 가중치 인접 행렬을 입력한다.
다음은 코드 : )
#include <stdio.h> #include <stdlib.h> #include <limits.h> //필요한 라이브러리를 추가합니다. //*다익스트라 알고리즘의 기초를 설정합니다.*// #define TRUE 1 //True일때 1로 정의합니다. #define FALSE 0 //False일때 0으로 정의합니다. #define MAX_VERTICES 100 //최대 정점의 수를 나타냅니다. #define INF 1000000 // 간선이 연결되어있지 않는 경우를 무한대로 나타냅니다. 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[]) //현재 distance배열에서 최소 가중치 값에 있는 노드를 골라 인덱스를 반환합니다. { int i, min, minpos; //각 노드를 나타내는 변수를 설정합니다. min = INT_MAX; //min에 INT_MAX(무한대와 유사, 간선이 연결되지 않은 경우)를 삽입합니다. minpos = -1; for (i = 0; i < n; i++) //최소값 min을 찾는 for문입니다. //방문한 적 없는 노드들에 대해 distance 배열의 값을 비교합니다. if (distance[i] < min && !found[i]) { //만약 현재 방문하지 않는 노드 중 i로까지의 거리가 현재 최소값 min보다 작다면, min = distance[i]; //최소 거리인 i로까지의 거리를 min으로 설정합니다. minpos = i; //최소값을 가진 노드의 인덱스 i를 minpos에 저장합니다. } return minpos; //최소 거리 노드 인덱스인 i를 반환합니다. } void print_status(GraphType* g) //최단 경로를 출력하는 함수 입니다. { static int step = 1; printf("STEP %d: ", step++); //첫번째 스텝에 1을 대입하여 출력하고 하나씩 늘려갑니다. printf("distance: "); for (int i = 0; i < g->n; i++) { //i가 n까지의 범위에서 하나씩 늘어가며 반복되는 for문입니다. if (distance[i] == INF) printf(" * "); //만약 거리가 무한대(간선이 연결되지 않은 경우)로 표시되어있다면 "*"을 출력하고, else printf("%2d ", distance[i]); //아니라면 거리값을 출력합니다. } printf("\n"); printf(" found: "); for (int i = 0; i < g->n; i++) //i가 n까지의 범위에서 하나씩 늘어가는 for문입니다. printf("%2d ", found[i]); //노드 인덱스 i를 방문했으면 1을, 방문하지 않았으면 0을 출력합니다. printf("\n\n"); } void shortest_path(GraphType * g, int start) //그래프에서 start노드부터의 최단 경로를 찾는 알고리즘입니다. { int i, u, w; for (i = 0; i < g->n; i++) /* 초기화 작업입니다.*/ //i가 0부터 n까지 하나씩 증가하며 반복되는 for문입니다. { distance[i] = g->weight[start][i]; //시작 정점 start를 기준으로 했을때 가중치로 distance 배열을 초기화합니다. found[i] = FALSE; //시작 전이므로 방문 여부를 False로 지정합니다. } found[start] = TRUE; /* 시작 정점을 방문 표시합니다*/ //시작 정점을 방문했으므로 방문 여부를 True로 지정합니다. distance[start] = 0; //시작 정점의 distance배열 값은 0입니다. for (i = 0; i < g->n - 1; i++) { //i가 0부터 n-1까지 하나씩 증가하며 반복되는 for문입니다. //위에서 시작 정점을 설정했으므로 하나를 뺀 n-1만큼 반복합니다. print_status(g); //그래프의 최단 경로를 출력합니다. u = choose(distance, g->n, found); //최소값의 인덱스를 u로 지정합니다. found[u] = TRUE; //현재 distance배열에서 최소값 인덱스인 u를 정점으로 선택합니다. //인덱스u를 방문 표시합니다. for (w = 0; w < g->n; w++) //가중치가 가장 적은 값을 가진 정점을 집합S에 추가한 뒤 계속하여 새롭게 발견되는 최소 가중치 정보를 수정해나갑니다. //w가 0부터 n까지 1씩 증가하며 반복되는 for문입니다. if (!found[w]) //아직 선택되지 않은 정점 w입니다. if (distance[u] + g->weight[u][w] < distance[w]) distance[w] = distance[u] + g->weight[u][w]; //만약 u까지의 최단 거리와 u에서 w의 거리를 합친 거리가 기존의 기준점에서 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 } } }; //[그림2 참고]그래프 g의 가중치 인접 행렬을 나타냅니다. shortest_path(&g, 0); return 0; }
위 코드 메인 함수의 가중치 인접 행렬을 나타낸 그래프는 다음 그림과 같다.
이 그래프의 집합 S와 distance의 초기값을 순서대로 구해볼 것 이다!
<1>
먼저 S에는 시작 정점인 ‘0’이 들어온다.
0과 인접한 정점들의 거리는 순서대로 [0, 7, 무한, 무한, 3, 10, 무한] 이다.
그리고 0과 인접한 정점들 중 가장 작은 거리값을 가진 4가 다음 정점으로 선택된다.
<2>
집합S에 4가 추가되고, 4와 인접한 정점들의 distance값이 갱신된다.
정점 1은 정점 4를 거치는 편이 더욱 빠르기 때문에 0부터 4까지의 거리값 ‘3’과 4부터 1까지의 거리값 ‘2’가 합쳐진 가리값 ‘5’로 갱신된다.
3은 4와 간선이 연결되어 있기 때문에 무한대 값을 벗어나 ‘14’로 갱신된다.
6의 값 또한 마찬가지!
distance값은 순서대로 [0, 5, 무한, 14, 3, 10, 8]이다.
<3>
다음은 0,4를 제외한 정점들 중 최소 가중치를 지닌 1이 선택됐다.
1과 연결된 정점 2는 9로 갱신됐다.
distance값은 순서대로 [0, 5, 9, 14, 3, 10, 8]이다.
<4>
다음은 0,4,1을 제외한 정점들 중 최소 가중치를 가진 6이 선택됐다.
6의 인접 정점들 중 3은 4를 거친 과정보다 6을 거쳐 오는 편이 더 최단 거리 이기 때문에 12로 갱신된다.
distance값은 순서대로 [0, 5, 9, 12, 3, 10, 8]이다.
<5>
다음은 0,4,1,6을 제외한 정점들 중 가장 가중치가 작은 2가 선택됐다.
2의 인접 정점인 3은 6을 거치는 것보다 2를 거쳐 오는 거리가 더 짧기 때문에 11로 갱신된다.
Distance 값은 순서대로 [0, 5, 9, 11, 3, 10, 8]이다.
<6>
다음은 0,4,1,6,2를 제외한 정점들 중 가장 가중치가 작은 5가 선택됐다.
더이상 갱신될 값이 보이지 않기 때문에 distance값이 유지된다.
<7>
다음은 마지막 정점 3이 집합 S에 추가된다.
더이상 갱신될 값 없이 distance값이 유지된다.
이와 같은 과정을 거친 코드의 출력 결과는 다음과 같이 정확한 distance값과 방문 여부 표시가 출력된다!
