C언어 dijkstra 그래프 최단 경로 찾기 알고리즘

이전 글에서 그래프에서 cycle이 만들어지지 않으며 모든 정점을 연결하는 MST를 kruskal 알고리즘으로 만들어보았다. 이번에는 그래프에서 시작 정점에서 특정 정점까지 최단거리로 연결하는 길을 찾는 방법을 알아볼 것이며 dijkstra 알고리즘을 이용할 것이다.

최단경로 찾기 알고리즘

Dijkstra의 최단 경로 알고리즘의 단계는 다음과 같다.

1. 집합에서 가장 짧은 경로의 정점 u를 집합에 추가
2. 집합에 없는 다른 정점까지의 거리 업데이트
   • u를 거쳐 가는 경로가 더 짧으면 해당 값으로 업데이트

이게 가능한 이유는 집합에서 가장 가까운 정점 u를 선택하면, u로 가는 더 가까운 길은 없기 때문이다.

https://ko.wikipedia.org/

C언어 구현 방법

그래프 구조체에는 vertex의 수 n과, 정점간 간선의 weight(거리)를 의미하는 2차원 배열 weight가 있다.

typedef struct GraphType {
	int n;	
	int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int distance[MAX_VERTICES];
int found[MAX_VERTICES];

정점까지의 거리를 distance 라는 1차원 배열로 선언
정점 간의 거리는 weight 라는 2차원 배열로 저장
정점을 모두 집합에 넣을 때까지 반복

• 집합에 가장 짧은 거리 정점 u 추가
• u의 모든 인접 정점에 대해
  • 거리 업데이트 (기존 distance가 짧은지, u 거쳐가는게 짧은지)

필요한 함수

1. choose 
   집합에 가장 가까운 정점을 찾는 함수
2. print_status
   현재 상태 출력 
   shortest_path 함수에서 각 단계별로 distance와 집합에 있는 정점을 보여줄 것
3. shortest_path
   한 정점씩 나아가며 distance를 업데이트 

함수

1) choose

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;
}

거리 배열, 정점의 수, 집합을 의미하는 found 배열을 인자로 받는다.
0~n까지 거리가 짧고 found[] 배열에 없으면
→ 최소 거리 업데이트, 정점 저장
→ 반복문으로 다 돌고 정점 반환

2) print_status

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");
}

상태만 보여줌

3) shortest_path

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];
	}

반복문을 이용해 distance 배열을 초기화, 그래프 구조체에서 weight 값을 이용해 거리를 알 수 있다. 간선이 없는 경우 INF로 나타날 것이다. 그리고 집합에는 현재 아무 정점도 없다는 의미로 found 배열 값을 전부 FALSE로 바꾼다.

그리고 시작하는 정점이 있기에 found 배열과 distance 배열을 재설정한다.

for 반복문으로 정점을 돌아가며 distance를 업데이트하면서 집합에 추가해줄 것이다. 기존에 만들어둔 choose 함수를 이용해 가장 가까운 정점을 찾아 u에 저장한다. found[u] = TRUE 로 집합에 정점 u를 넣는다. 그리고 반복문으로 u의 인접 정점 중 집합에 없는(!found[w]) 정점 w까지 거리(distance[w])를 업데이트 한다.

• u를 거쳐서 w까지 가는 거리와 기존 distance[w]를 비교해 작은 값으로 업데이트 한다.