ALGORITHM/이론

최단 경로 알고리즘: Dijkstra, Floyd

연듀 2022. 12. 6. 14:29

Dijkstra 최단 경로 알고리즘

 

하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

 

 

n개의 정점이 있다면 O(n^2)의 시간복잡도를 가진다.

 

 

#include<stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L

typedef struct GraphType {
	int n; // 정점의 개수
	int weight[MAX_VERTICES][MAX_VERTICES];
}GraphType;

int distance[MAX_VERTICES]; // 시작 정점으로부터의 최단경로 거리
int found[MAX_VERTICES]; // 방문한 정점 표시

// 선택되지 않은 정점 중 distance 값이 가장 작은 정점의 인덱스 찾기
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: \n", 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; // 시작 정점 거리는 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]) // u->w 거리가 더 짧다면
					distance[w] = distance[u] + g->weight[u][w];; // 거리 갱신
	}
}

int main() {
	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;
}
STEP 1:
distance:  0  7  *  *  3 10  *
found   :  1  0  0  0  0  0  0

STEP 2:
distance:  0  5  * 14  3 10  8
found   :  1  0  0  0  1  0  0

STEP 3:
distance:  0  5  9 14  3 10  8
found   :  1  1  0  0  1  0  0

STEP 4:
distance:  0  5  9 12  3 10  8
found   :  1  1  0  0  1  0  1

STEP 5:
distance:  0  5  9 11  3 10  8
found   :  1  1  1  0  1  0  1

STEP 6:
distance:  0  5  9 11  3 10  8
found   :  1  1  1  0  1  1  1

 

 

Floyd 최단 경로 알고리즘

 

그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘

3중 반복문이 실행되므로 시간 복잡도가 O(n^3)이다. 

#include<stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L

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("===========================\n");
	for (i = 0; i < g->n; i++) {
		for (j = 0; j < g->n; j++) {
			if (A[i][j] == INF)
				printf(" * ");
			else printf("%2d ", A[i][j]);
		}
		printf("\n");
	}
	printf("===========================\n");
}

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][j] + A[k][j] < A[i][j])
					A[i][j] = A[i][k] + A[k][j];
		printA(g);
	}
}


int main() {
	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;
}
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================
===========================
 0  7  *  *  3 10  *
 7  0  4 10  2  6  *
 *  4  0  2  *  *  *
 * 10  2  0 11  9  4
 3  2  * 11  0  *  5
10  6  *  9  *  0  *
 *  *  *  4  5  *  0
===========================

 

두 개의 정점 사이의 최단 경로를 찾는 Dijkstra의 알고리즘은 시간 복잡도가 O(n^2)이므로, 

모든 정점 쌍의 최단 경로를 구하려면 알고리즘을 n번 반복해야하므로 전체 복잡도는 O(n^3)이다.

 

한번의 모든 정점간의 최단 경로를 구하는 Floyd의 알고리즘은 3중 반복문이 실행되므로 시간복잡도가 O(n^3)이고,

Dijkstra 알고리즘과 비교해 차이는 없다고 할 수 있다.

그러나 Floyd알고리즘은 매우 간결한 반복구문을 사용하므로 Dijkstra 알고리즘보다 빨리 모든 정점간의 최단 경로를 찾을 수 있다. 

 

 

저작자표시

'ALGORITHM > 이론' 카테고리의 다른 글

[알고리즘] 이분 탐색(Binary Search)  (0) 2022.12.29
정렬 알고리즘: 선택, 삽입, 버블, 쉘, 합병, 퀵 정렬  (0) 2022.12.06
최소 비용 신장 트리(MST): Kruskal, Prim 알고리즘  (0) 2022.12.06
그래프 탐색 알고리즘: BFS, DFS  (0) 2022.10.19

'ALGORITHM/이론'의 다른글

  • 현재글최단 경로 알고리즘: Dijkstra, Floyd

관련글

티스토리툴바