최단경로 알고리즘

에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.
이 합이 가장 작을 때 ‘최단 경로’라고 한다.

다익스트라 알고리즘

음수 가중치가 없다고 가정한 단일-소스 최단 경로 알고리즘, prim알고리즘처럼 S가 처음 주어지고 T영역으로 S를 확대해 나가는 알고리즘
(Tip) s'(소스)로부터 해당 정점까지 거리를 합하여 작은 것을 선택하는 것이 포인트

구현 방법 및 시간 복잡도

prim알고리즘의 테이블 논리를 그대로 이용함. -> O(n^2)
단, w열을 (s’로부터 누적해서 계산한 값)으로 업데이트 함.

prim table의 w열은 Length열로, vertex열은 parent열로 변경됨을 주의!!

다익스트라 알고리즘 구현

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

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000

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

int L[MAX_VERTICES]; // <테이블의 w열> , 원소: s집합에서 해당 정점까지의 누적 거리 
int selected[MAX_VERTICES]; //  <테이블의 s/t열> , 선택되면 s집합에 속함 

// 현재 테이블(s/t,L) 상태 출력 
void print_status(GraphType* g) {
	printf("\nS/T:    ");
	for (int i = 0; i < g->n; i++)
		printf("%2d ", selected[i]);
	printf("\n");
	printf("Length: ");
	for (int i = 0; i < g->n; i++) {
		if (L[i] == INF)
			printf("INF ");
		else
			printf("%2d ", L[i]);
	}
	printf("\n");
}

// s집합에 속하지 않으면서 최소 w[v] 값을 갖는 정점을 반환
int get_min_vertex(int n) {
	int v, i;
	// 선택되지 않은 정점을 선택 (v정점 지정) 
	for (i = 0; i < n; i++) {
		if (!selected[i]) {
			v = i;
			break;
		}
	}
	// v정점의 w값과 나머지 정점들의 w값을 비교하면서 최소 w값을 갖는 정점 구하기 (선택된 것은 제외) 
	for (i = 0; i < n; i++) {
		if (!selected[i] && (L[i] < L[v]))
			v = i;
	}
	return v;
}

void shortest_path(GraphType* g, int start) {
	int i, u, w;

	// s집합이 시작 정점(0)만 있을 때 테이블을 생성  <정점 1개 선택 됨>
	for (i = 0; i < g->n; i++) {
		L[i] = g->weight[start][i];
		selected[i] = FALSE;
	}
	selected[start] = TRUE;

	// s집합을 확대해 나가면서 테이블을 업데이트 <선택할 정점이 없거나, n-1개의 정점이 선택될 때까지> 
	for (i = 0; i < g->n - 1; i++) {
		print_status(g);
		// L배열에서 가중치가 가장 작은 정점 선택 (s에 속하지 않은 정점들로 한정) 
		u = get_min_vertex(g->n);
		selected[u] = TRUE;
		if (L[u] == INF) {
			printf("-> 선택할 정점이 없음\n");
			return;
		}
		else
			printf("-> 정점 %d 선택\n", u); 

		// s집합과 인접한 정점들로 L배열 업데이트
		for (w = 0; w < g->n; w++) {
			if (!selected[w]) {
				// u정점을 기준으로 인접한 것을 찾음 <u정점 말고 다른 정점도 s집합에 속하지만 같은 배열을 업데이트하는 개념이므로, 이미 처리가 된 상태임>
				if (g->weight[u][w] != INF) {
					// prim때와는 달리 누적 거리를 계산함 
					if (L[u] + g->weight[u][w] < L[w])
						L[w] = L[u] + g->weight[u][w];
				}
			}
		}
	}
}

int main(void) {

	// 가중치를 포함한 방향 그래프 (연결 못하면 INF)
	GraphType g = {
		6,{
			{0,50,10,INF,45,INF},
			{INF,0,15,INF,10,INF},
			{20,INF,0,15,INF,INF},
			{INF,20,INF,0,35,INF},
			{INF,INF,INF,30,0,INF},
			{INF,INF,INF,3,INF,0},
		}
	};
	shortest_path(&g,0);
	return 0;
}