-> 블로그 이전

[Data Structure] 최단경로 - Dijkstra Algorithm

2021. 12. 25. 14:32ㆍMajor`/자료구조

최단경로

- 정점 i ~ 정점 j까지 간선들의 weight 합이 최소가 되는 경로

 

Dijkstra

  • 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로 

Floyd

  • 모든 정점 ~ 다른 모든 정점까지의 최단 경로

 

 

 

Dijkstra Algorithm

- 탐욕적 방법 (greedy method) 이용

- 특정 시작 정점 ~ 다른 모든 정점까지의 최단 경로 계산

- 가중치가 음수가 아닐 때 정상적으로 작동

- Dijkstra → Greedy → DP(최단경로 + 길찾기) / 매 상황에서 가장 비용이 적은 최선의 정점 선택

- 시작정점으로부터 거리를 저장하는 distance[] 1차원 배열이 필요

- O(n²)

 

  1. 시작 정점(v) 선택
  2. 시작 정점으로부터 다른 모든 정점까지의 distance 업데이트 (한 번에 갈 수 없으면 INF로 초기화)
  3. INF가 아닌 인접 정점 중, 최단거리의 정점(w) 선택
  4. v~w를 거쳐서 다른 모든 정점(s)까지의 distance 업데이트 → distance[s], distance[w] + distance[w][s] 중 더 작은 값으로 update (v~s(한 번에) or v~w~s(w를 거쳐서)

 

 

※ Example

Vertex 0 1 2 3 4 5 6
distance INF INF INF INF INF INF INF
select X X X X X X X

- 시작 정점 : 0

  • 시작 정점에서의 가중치 = 0으로 설정 (g->weight[start][start] = 0)
Vertex 0 1 2 3 4 5 6
distance 0 15 INF 54 24 INF INF
select O X X X X X X
  • 0에서부터 weight가 가장 작은 정점 1 선택
  • 이때, 0~1~3 weight(52)가 0~3 weight(54)보다 작기 때문에 distance[3]을 더 작은 값으로 update
Vertex 0 1 2 3 4 5 6
distance 0 15 INF 52 24 INF 58
select O O X X X X X
  • 0에서부터 weight가 가장 작은 정점 4 선택
  • 0~4~2 weight(86) < 0~2 weight(INF) / 0~4~5 weight(43) < 0~5 weight(INF)
Vertex 0 1 2 3 4 5 6
distance 0 15 86 52 24 43 58
select O O X X O X X
  • 0에서부터 weight가 가장 작은 정점 5 선택
  • 0~5~2 weight(60) < 0~2 weight(86)
Vertex 0 1 2 3 4 5 6
distance 0 15 60 52 24 43 58
select O O X X O O X
  • 0에서부터 weight가 가장 작은 정점 3 선택
Vertex 0 1 2 3 4 5 6
distance 0 15 60 52 24 43 58
select O O X O O O X
  • 0에서부터 weight가 가장 작은 정점 6 선택
Vertex 0 1 2 3 4 5 6
distance 0 15 60 52 24 43 58
select O O X O O O O
  • 0에서부터 weight가 가장 작은 정점 2 선택
Vertex 0 1 2 3 4 5 6
distance 0 15 60 52 24 43 58
select O O O O O O O
  • 정점 0으로부터 각 정점까지의 최단경로 탐색 알고리즘 종료

▶ Dijkstra Algorithm Code

int distance[MAX_VERTEX];
int selected[MAX_VERTEX];

void init_distance(int distance[]) {
	for (int i = 0; i < MAX_VERTEX; i++)
		distance[i] = INF;
}

void init_selected(int selected[]) {
	for (int i = 0; i < MAX_VERTEX; i++)
		selected[i] = FALSE;
}
  • distance, selected 배열을 각각 INF, FALSE로 초기화
#define min(a, b) ((a<b)?a:b)

int select_min(int n) {
	int min = INF;
	int v=0;
	for (int i = 0; i <n; i++) {
		if (selected[i] == FALSE && distance[i] < min) {
			min = distance[i];
			v = i;
		}
	}
	return v;
}

void dijkstra(graph* g, int v) {
	init_distance(distance);
	init_selected(selected);

	int w, s; // w = v의 인접 정점, s = w의 인접 정점

	distance[v] = 0;
	g->weight[v][v] = 0;

	for (int i = 0; i < g->n; i++) {
		distance[i] = g->weight[v][i];
	}
	
	for (int i = 0; i < g->n; i++) {
		w = select_min(g->n);
		selected[w] = TRUE;
		printf("\n");
		printf("Step %d : 정점 %d 선택\n", i+1, w);

		for (s = 0; s < g->n; s++) {
			if (g->weight[w][s] != INF && selected[s] == FALSE) {
				distance[s] = min(distance[s], distance[w] + g->weight[w][s]);
			}
		}

		printf("%-8s >> [ ", "distance");
		for (int i = 0; i < g->n; i++) {
			if (distance[i] == INF)
				printf("%s ", "*");
			else
				printf("%d ", distance[i]);
		}
		printf("]\n");

		printf("%-8s >> [ ", "select");
		for (int i = 0; i < g->n; i++) {
			if (selected[i] == TRUE)
				printf("%s ", "O");
			else
				printf("%s ", "X");
		}
		printf("]\n");
	}
	printf("--------------------------------------------\n");
}

Code 6~12

  • 선택되지 않은 정점들에 대해, 가장 작은 weight를 가지고 있는 정점 탐색 후 return

Code 21~22

  • 함수의 매개변수 v는 시작 정점이기 때문에, distance[v] = 0으로 설정해주고, 해당 정점의 weight (g->weight[v][v])또한 0으로 설정해준다

Code 24~26

  • 시작 정점으로부터 모든 정점들에 대해 각각 distance 설정
  • edge가 존재하면 해당 weight
  • edge가 없으면 INF

Code 29~30

  • 선택되지 않은 정점 중 weight가 가장 작은 정점을 선택하고, 해당 정점은 selected - TRUE로 표시

Code 34~38

  • Code 27~28에서 선택한 정점(w)로부터 edge가 존재하고, 선택되지 않은 모든 정점들 s에 대해서 weight(v~s), weight(v~w~s)중, 더 짧은 weight를 새로 갱신
  • distance[s] = min(distance[s], distance[w] + g->weight[w][s]) 

▶ Full Code

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

// Dijkstra ShortestWay Algorithm
#define TRUE 1
#define FALSE 0
#define MAX_VERTEX 100
#define INF 99999

#define min(a, b) ((a<b)?a:b)

int distance[MAX_VERTEX];
int selected[MAX_VERTEX];

void init_distance(int distance[]) {
	for (int i = 0; i < MAX_VERTEX; i++)
		distance[i] = INF;
}

void init_selected(int selected[]) {
	for (int i = 0; i < MAX_VERTEX; i++)
		selected[i] = FALSE;
}

typedef struct graph {
	int n; // 정점 개수
	int vertex[MAX_VERTEX];
	int weight[MAX_VERTEX][MAX_VERTEX];
}graph;

graph* create() {
	return (graph*)malloc(sizeof(graph));
}

void init_graph(graph* g) {
	g->n = 0;
	for (int r = 0; r < MAX_VERTEX; r++) {
		for (int c = 0; c < MAX_VERTEX; c++) {
			g->weight[r][c] = INF;
		}
	}
}

int is_full(graph* g) {
	return g->n == MAX_VERTEX;
}

int bool_vertex(graph* g, int v) {
	int flag = FALSE;
	for (int i = 0; i < g->n; i++) {
		if (g->vertex[i] == v)
			flag = TRUE;
	}
	if (flag == TRUE) return TRUE;
	else return FALSE;
}

void insert_vertex(graph* g, int v) {
	if (is_full(g))
		return;
	else if (bool_vertex(g, v) == TRUE)
		return;
	g->vertex[g->n++] = v;
}

void insert_edge(graph* g, int start, int end, int weight) {
	// 무방향 그래프를 조건으로
	if (bool_vertex(g, start) == FALSE || bool_vertex(g, end) == FALSE)
		return;
	g->weight[start][end] = weight;
	g->weight[end][start] = weight;
}

int select_min(int n) {
	int min = INF;
	int v=0;
	for (int i = 0; i <n; i++) {
		if (selected[i] == FALSE && distance[i] < min) {
			min = distance[i];
			v = i;
		}
	}
	return v;
}

void dijkstra(graph* g, int v) {
	init_distance(distance);
	init_selected(selected);

	int w, s; // w = v의 인접 정점, s = w의 인접 정점

	distance[v] = 0;
	g->weight[v][v] = 0;

	for (int i = 0; i < g->n; i++) {
		distance[i] = g->weight[v][i];
	}
	
	for (int i = 0; i < g->n; i++) {
		w = select_min(g->n);
		selected[w] = TRUE;
		printf("\n");
		printf("Step %d : 정점 %d 선택\n", i+1, w);

		for (s = 0; s < g->n; s++) {
			if (g->weight[w][s] != INF && selected[s] == FALSE) {
				distance[s] = min(distance[s], distance[w] + g->weight[w][s]);
			}
		}

		printf("%-8s >> [ ", "distance");
		for (int i = 0; i < g->n; i++) {
			if (distance[i] == INF)
				printf("%s ", "*");
			else
				printf("%d ", distance[i]);
		}
		printf("]\n");

		printf("%-8s >> [ ", "select");
		for (int i = 0; i < g->n; i++) {
			if (selected[i] == TRUE)
				printf("%s ", "O");
			else
				printf("%s ", "X");
		}
		printf("]\n");
	}
	printf("--------------------------------------------\n");
}

int main(void) {
	graph* g;
	g = create(); init_graph(g);

	for (int i = 0; i < 7; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 1, 15);
	insert_edge(g, 0, 3, 54);
	insert_edge(g, 0, 4, 24);
	insert_edge(g, 1, 3, 37);
	insert_edge(g, 1, 4, 77);
	insert_edge(g, 1, 6, 43);
	insert_edge(g, 2, 4, 62);
	insert_edge(g, 2, 5, 17);
	insert_edge(g, 2, 6, 45);
	insert_edge(g, 3, 6, 31);
	insert_edge(g, 4, 5, 19);

	printf("--------------------------------------------\n");
	printf("Dijkstra Algorithm\n");
	printf("--------------------------------------------\n");
	printf("시작 정점 : 0\n");
	dijkstra(g, 0);
	printf("시작 정점 : 2\n");
	dijkstra(g, 2);

	return 0;
}

저작자표시 변경금지

관련글

댓글 0

티스토리툴바