【코딩】 C 언어로 최단경로 알고리즘 (Dijkstra 및 Floyd 알고리즘)

C 언어로 최단경로 알고리즘 (Dijkstra 및 Floyd 알고리즘)

 

추천글 : 【C 언어】 C 언어 목차

---

1. 거리 개념 [본문]

2. 최단경로 알고리즘 [본문]

---

 

1. 거리 개념 [목차]

⑴ 거리 함수(distance function, metric) : 거리를 정의

 

 

⑵ 거리 함수의 종류

 

 

2. 최단경로 알고리즘 [목차]

⑴ 문제 상황 : 예를 들면 0번 → 5번으로 가는 경로는 6만큼의 비용이 듦. 즉, 6만큼의 거리를 이동해야 함

 

Table. 1. 문제 상황

 

⑵ 다익스트라 알고리즘(Dijkstra) : 각 노드에서 Bellman 방정식을 풀고 이미 조회한 노드에 대해 값을 저장. 2중 for 문이 특징 

 

#include <stdio.h>
#include <stdlib.h>
#define Count_Vertice 6
#define Far_Distance 2000
// W[i][j]는 i에서 j까지의 직행거리, Far_Distance는 바로 갈 수 없는 경우를 표시
int W[Count_Vertice][Count_Vertice] = {
    {0,          Far_Distance, 2, 3, 3, 6},
    {Far_Distance, 0,          Far_Distance, 4, 2, Far_Distance},
    {10,         2,            0, 5, 1, Far_Distance},
    {Far_Distance, Far_Distance, 4, 0, Far_Distance, 2},
    {5,          9,            Far_Distance, 4, 0, 3},
    {Far_Distance, Far_Distance, Far_Distance, 4, Far_Distance, 0},
};

// dist[i] : 시작점에서 i까지의 최단거리
// prev[i] : 시작점에서 i까지 최단경로 중 i의 바로 이전 정점
int dist[Count_Vertice];
int prev_v[Count_Vertice];
int visited[Count_Vertice];

void Dijkstra(int start) {
    int i, j;
    // 초기화
    for (i = 0; i < Count_Vertice; i++) {
        dist[i] = W[start][i];   // 시작점에서 바로 가는 거리 (없으면 Far_Distance)
        if (W[start][i] < Far_Distance && i != start)
            prev_v[i] = start;   // 바로 갈 수 있으면 start가 직전 정점
        else
            prev_v[i] = -1;      // 경로 없음
        visited[i] = 0;
    }
    dist[start] = 0;
    prev_v[start] = -1; // 시작점은 이전 정점 없음

    // 정점 수만큼 반복
    for (i = 0; i < Count_Vertice; i++) {
        int u = -1;
        int min_dist = Far_Distance + 1;

        // 방문하지 않은 정점 중 dist가 가장 작은 정점 u 선택
        for (j = 0; j < Count_Vertice; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }

        // 더 이상 갈 수 있는 정점이 없으면 종료
        if (u == -1) break;

        visited[u] = 1;
        // u를 거쳐서 가는 경로로 갱신 시도
        for (j = 0; j < Count_Vertice; j++) {
            if (!visited[j] && W[u][j] < Far_Distance) { // u -> j 간선이 있을 때
                if (dist[j] > dist[u] + W[u][j]) {
                    dist[j] = dist[u] + W[u][j];
                    prev_v[j] = u;
                }
            }
        }
    }
}

// 시작점 a에서 도착점 b까지 경로를 재귀적으로 출력
void Print_Path(int a, int b) {
    if (a == b) {
        printf("%d ", a);
    } else if (prev_v[b] == -1) {
        // 경로가 없을 때
        printf("(경로 없음) ");
    } else {
        // b의 직전 정점부터 먼저 출력한 뒤 b 출력
        Print_Path(a, prev_v[b]);
        printf("%d ", b);
    }
}

int main(void) {
    int a, b;
    printf("출발점과 도착점을 입력하시오. (0 ~ %d)\n", Count_Vertice - 1);
    if (scanf("%d %d", &a, &b) != 2) {
        printf("입력 오류\n");
        return 1;
    }
    if (a < 0 || a >= Count_Vertice || b < 0 || b >= Count_Vertice) {
        printf("정점 번호 범위를 벗어났습니다.\n");
        return 1;
    }
    // a를 시작점으로 다익스트라 실행
    Dijkstra(a);
    if (dist[b] >= Far_Distance) {
        // 도달 불가
        printf("정점 %d에서 정점 %d로 가는 경로가 없습니다.\n", a, b);
    } else {
        printf("최단거리 : %d\n", dist[b]);
        printf("최단경로 : ");
        Print_Path(a, b);
        printf("\n");
    }
    return 0;
}

 

⑶ 플로이드 알고리즘(Floyd, Floyd–Warshall) : 3중 for 문이 특징. Dijkstra 알고리즘보다 더 직관적

 

#include <stdio.h>
#include <stdlib.h>
#define Count_Vertice 6
#define Far_Distance 2000

int W[Count_Vertice][Count_Vertice] = {
	// W[i][j]는 i에서 j까지의 직행거리, Far_distance란 큰 수는 바로 갈 수 없는 경우를 표시
    {0, Far_Distance, 2, 3, 3, 6},
    {Far_Distance, 0, Far_Distance, 4, 2, Far_Distance},
    {10, 2, 0, 5, 1, Far_Distance},
    {Far_Distance, Far_Distance, 4, 0, Far_Distance, 2},
    {5, 9, Far_Distance, 4, 0, 3},
    {Far_Distance, Far_Distance, Far_Distance, 4, Far_Distance, 0},
};

int D[Count_Vertice][Count_Vertice]; // D[i][j]는 i에서 j까지 가는 최소 거리를 저장
int P[Count_Vertice][Count_Vertice]; // P[i][j]는 i에서 j까지 가는 데 거치는 최고 차수 정점을 저장

void Floyd(){
	int i, j, k;
	for(i=0; i < Count_Vertice; i++) // 배열 초기화
		for(j=0; j < Count_Vertice; j++){
			P[i][j] = -1;
			D[i][j] = W[i][j];
		}
	for(k=0; k < Count_Vertice; k++)
		for(i=0; i < Count_Vertice; i++)
			for(j=0; j < Count_Vertice; j++)
				if(D[i][j] > D[i][k] + D[k][j]){
				/* k를 거칠 시 D[i][j]가 더 짧아지는 경우 */
					D[i][j] = D[i][k] + D[k][j];
					P[i][j] = k;
				}
}

void Print_Path(int a, int b){ // Print_Path[i][j]에서 i와 j는 출력하지 않음을 주의
	if(P[a][b] != -1) { // P[a][b] = -1 "=" a에서 바로 b로 가는 것이 최단거리
		Print_Path(a, P[a][b]);
		printf("%d ", P[a][b]);
		Print_Path(P[a][b], b);
	}
}

int main(int argc, char *argv[]){
	Floyd();
	int a, b;
	printf("출발점과 도착점을 입력하시오. (0 ~ %d)\n", Count_Vertice - 1);
	scanf("%d %d", &a, &b);
	printf("최단거리 : %d\n", D[a][b]);
	printf("최단경로 : ");
	printf("%d ", a); Print_Path(a, b);
	if(D[a][b] != 0) printf("%d", b); // D[a][b] = 0 "=" a = b
	return 0;
}

 

입력: 2013.12.13 22:55