Dijkstra Algorithm[C]

다익스트라 알고리즘

: Dynamic Programming을 활용한 최단 경로 탐색 알고리즘

"현재까지 알고있던 최단경로를 계속해서 갱신해나가는 알고리즘"

: 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌

=>이때 최단거리는 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기에 DP활용 알고리즘이다

 

 

ver1)선형탐색

1. 동작 방식

 

1) 출발 노드 설정(start 변수)

2) 초기에 출발 노드를 기준으로 각 노드의 최소 비용 저장

3) 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 => 선형탐색과 힙 이용한 두 가지 구현방식 존재

4) 해당 노드를 거쳐 특정 노드로 가는 경우를 고려하여 최소 비용 갱신

5) 3~4) 과정 반복

=> 이때 반복문을 이용하여 방문하지 않는 모든 노드들을 방문

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

#define INF 10000

int MinCost(bool* visited, int* distance, int size, int now) {
	int max = INF;
	int idx;
	for (int i = 0; i < size; i++) {
		if (visited[i] != true && i != now) {
			if (max > distance[i]) {
				idx = i;
			}
		}
	}
	return idx;
}

void PrintGraph(int* distance, int size, int start) {
	printf("%d번 노드에서 출발한 다익스트라 경로 : ", start+1);
	for (int i = 0; i < size; i++) {
		if (i) {
			printf("->");
		}
		printf("%d ", distance[i]);
	}
}

void Dijkstra(int(*g)[6], int start) {
	bool visited[6] = {false,};
	int distance[6] = { 0 };
	int size = sizeof(distance) / sizeof(int);
	int now;
	for (int i = 0; i < 6; i++) {
		distance[i] = g[start][i];
	}
	//1번째노드 : 초기화과정이므로 코드작성 필요 x
	visited[0] = true;
	now = 0;
	for (int i = 1; i < size; i++) {
		now = MinCost(visited, distance, size,now);
		visited[now] = true;
		for (int j = 0; j < size; j++) {
			if (g[now][j] + distance[now] < distance[j]) {
				distance[j] = g[now][j] + distance[now];
			}
		}
	}
	PrintGraph(distance, size, start);
}




int main() {
	int a[6][6] = { {0,2,5,1,INF,INF},{2,0,3,2,INF,INF},{5,3,0,3,1,5},
		{1,2,3,0,1,INF},{INF,INF,1,1,0,2},{INF,INF,5,INF,2,0} };

	for (int i = 0; i < 6; i++) {
		printf("\n");
		Dijkstra(a, i);
	}

	getchar();
	return 0;
}

ver2) 힙 구현

=> distance 값이 가장 작은 정점을 매번 구할때 선형탐색을 이용하면 시간복잡도가 O(n^2)이므로 힙정렬 알고리즘을 이용한다

=> 힙정렬의 시간복잡도는 O(nlogn)

cf> 힙은 완전이진트리를 기반으로 하기에 정점의 갯수가 n개라면 이진트리의 높이는 logn이기에 삽입/삭제 수행할 때 시간복잡도는 O(logn)이기에 최종적으로 O(nlogn)

: pos 배열을 생성하여 각 노드의 힙에서의 인덱스를 저장하고 노드의 distance가 바뀔때마다 업데이트해주는 방식으로 힙구현하였다.   

1. 동작 방식

1) 출발 노드를 제외하고 모든 distance 배열을 INF로 초기화

2) 반복문을 통해 모든 노드를 방문하여 출발 노드를 기준으로 각 노드의 최소 비용 저장

- distance 값이 INF인 경우 : 해당 노드 힙트리에 삽입

- distance 값이 INF가 아닌 경우 : 이미 힙트리에 존재하는 노드이기에 distance 값 갱신하고 다시 힙 최적화 (pos 배열 이용)

3) 가장 비용이 적은 노드 우선순위 큐 이용하여 꺼냄

4) 공백 트리가 될때까지 수행 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#define NODE_COUNT 7 //힙 구현때문에 
#define INF 100000

int pos[NODE_COUNT - 1];

void init() {
	for (int i = 0; i < NODE_COUNT - 1; i++) {
		pos[i] = -1;
	}
}


typedef struct _NODE_ {
	int vertex;
	int distance;
	
}NODE;

typedef struct _HEAP_TREE_ {
	NODE* heap[NODE_COUNT];
	int n; //노드의 갯수
}HEAP_TREE;

HEAP_TREE* MakeHeap() {
	HEAP_TREE* heap = (HEAP_TREE*)calloc(1, sizeof(HEAP_TREE));
	assert(heap != NULL);

	return heap;
}

void Change(int idx1, int idx2, int v1, int v2) {
	pos[v1] = idx2;
	pos[v2] = idx1;
}

void InsertNode(HEAP_TREE* h, int vertex, int distance) {
	NODE* newNode = (NODE*)calloc(1, sizeof(NODE));
	assert(newNode != NULL);


	if (h->n == NODE_COUNT - 1) {
		printf("힙트리는 이미 가득차있습니다\n");
		return;
	}
	else {
		newNode->vertex = vertex;
		newNode->distance = distance;
		if (h->n == 0) {
			h->n++;
			h->heap[h->n] = newNode;
			pos[vertex] = h->n;
		}
		else {
			h->n++;
			int idx = h->n;
			h->heap[idx] = newNode;
			pos[vertex] = h->n;
			while (idx != 1 && h->heap[idx / 2]->distance > h->heap[idx]->distance) {
				Change(idx, idx / 2, vertex, h->heap[idx / 2]->vertex);
				NODE* temp;
				temp = h->heap[idx];
				h->heap[idx] = h->heap[idx / 2];
				h->heap[idx / 2] = temp;
				
				idx /= 2;
				
			}
		}
	}
}

int DeleteNode(HEAP_TREE* h) {
	
	int next = h->heap[1]->vertex;
	pos[next] = -1;
	if (h->n == 1) {
		h->n--;
		return next;
	}
	else {
		h->heap[1] = h->heap[h->n];
		pos[h->heap[1]->vertex] = 1;
		h->n--;

		int idx = 1;
		while (idx * 2 <= h->n && h->heap[idx * 2]->distance < h->heap[idx]->distance) {
			int child = idx * 2;
			if (h->heap[child]->distance > h->heap[child + 1]->distance) {
				child = child + 1;
			}
			Change(idx, child, h->heap[idx]->vertex, h->heap[child]->vertex);
			NODE* temp = h->heap[child];
			h->heap[child] = h->heap[idx];
			h->heap[idx] = temp;

			
			idx = child;
		}
	}
	

	return next;
}

void UpdateNode(HEAP_TREE* h, int vertex, int distance) {
	int id = pos[vertex];
	NODE* curNode = h->heap[id];
	curNode->distance = distance;

	

	if (id !=1 && h->heap[id/2]->distance > curNode->distance) {
		int idx = id;
		while (idx != 1 && h->heap[idx / 2]->distance > h->heap[idx]->distance) {
			Change(idx, idx / 2, h->heap[idx]->vertex, h->heap[idx / 2]->vertex);
			NODE* temp;
			temp = h->heap[idx];
			h->heap[idx] = h->heap[idx / 2];
			h->heap[idx / 2] = temp;
			
			idx /= 2;
			
		}
	}
	else if (id *2 <= h->n && h->heap[id*2]->distance < curNode->distance) {
		int idx = id;
		while (idx * 2 <= h->n && h->heap[idx * 2]->distance < h->heap[idx]->distance) {
			int child = idx * 2;
			if (h->heap[child]->distance > h->heap[child + 1]->distance) {
				child = child + 1;
			}
			Change(idx, child, h->heap[idx]->vertex, h->heap[child]->vertex);
			NODE* temp = h->heap[child];
			h->heap[child] = h->heap[idx];
			h->heap[idx] = temp;
		
			idx = child;
		}
	}
	else {
		return;
	}
}

void PrintHeap(HEAP_TREE* h) {
	printf("\n힙 출력\n");
	for (int i = 1; i <= h->n; i++) {
		printf("(vertex: %d, distance: %d)\n", (h->heap[i]->vertex), h->heap[i]->distance);
	}
}

void PrintDistance(int* distance) {
	
	for (int i = 0; i < NODE_COUNT - 1; i++) {
		printf("%d ", distance[i]);
	}
}

void PrintPos() {
	printf("\npos: ");
	for (int i = 0; i < NODE_COUNT - 1; i++) {
		printf("%d ", pos[i]);
	}
	printf("\n");
}

void Dijkstra(HEAP_TREE* h, int(* a)[NODE_COUNT - 1], int* distance, int start) {
	distance[start] = 0;
	for (int i = 0; i < NODE_COUNT - 1; i++) {
		if (i != start) {
			distance[i] = INF;
		}
	}
	InsertNode(h, start, 0);

	while (h->n != 0) {
		int now = DeleteNode(h);
		for (int i = 0; i < NODE_COUNT - 1; i++) {
			if (a[now][i] + distance[now] < distance[i]) {
				int d = a[now][i] + distance[now];
				if (distance[i] == INF) {
					InsertNode(h, i, d);
				}
				else {
					UpdateNode(h, i, d);
				}
				distance[i] = d;

			}
			/*PrintHeap(h);
			PrintDistance(distance);
			PrintPos();*/
		}

	}

	printf("\n다익스트라 구현 경로 : ");
	PrintDistance(distance);

}



int main() {

	int a[NODE_COUNT - 1][NODE_COUNT - 1] = { {0,2,5,1,INF,INF},{2,0,3,2,INF,INF},{5,3,0,3,1,5},
		{1,2,3,0,1,INF},{INF,INF,1,1,0,2},{INF,INF,5,INF,2,0} };
	


	
	
	for (int i = 0; i < NODE_COUNT - 1; i++) {
		HEAP_TREE* heap = MakeHeap();
		init();
		int* distance = (int*)calloc(NODE_COUNT - 1, sizeof(int));
		assert(distance != NULL);
		Dijkstra(heap, a, distance, i);
	}



	getchar();
	return 0;
}

 

 

 

 

 

---

개선한 버전)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <memory.h>

#define VERTEX_SIZE 7
#define INF 100000

typedef struct _HEAP_NODE_ {
	int node; //노드의 번호 저장
	int distance; //가중치 값 저장(힙트리의 정렬조건)
}HEAP_NODE;

typedef struct _HEAP_TREE_ {
	HEAP_NODE* tr[VERTEX_SIZE + 1];
	int n; //노드의 갯수 
	int pos[VERTEX_SIZE+1]; //힙트리에 존재하지않는다면 0 (힙트리는 인덱스 1부터 존재함)
}HEAP_TREE;



void swap_node(HEAP_TREE * heap,HEAP_NODE * node1, HEAP_NODE * node2) { //힙트리에서의 위치 정보만 변경하는 함수 
	//만약 3번 노드가 7번째에 있고 2번 노드가 4번째에 있다면,
	//3번 노드는 4번째로 2번 노드는 7번째로
	int temp = heap->pos[node1->node];
	heap->pos[node1->node] = heap->pos[node2->node];
	heap->pos[node2->node] = temp;

}

void Insert_Node(HEAP_TREE* heap, HEAP_NODE * node) {
	if (heap->n == VERTEX_SIZE) {
		printf("더이상 노드를 삽입할 수 없습니다\n");
		return;
	}
	else {
		heap->n++;
		heap->tr[heap->n] = node;
		heap->pos[node->node] = heap->n;
		int idx = heap->n;
		while (idx != 1 && heap->tr[idx / 2]->distance > node->distance) {
			swap_node(heap, heap->tr[idx / 2], heap->tr[idx]);
			HEAP_NODE* temp = heap->tr[idx / 2];
			heap->tr[idx / 2] = heap->tr[idx];
			heap->tr[idx] = temp;
			idx /= 2;
		}
	}
}

HEAP_NODE* Delete_Node(HEAP_TREE* heap) {
	if (heap->n == 0) {
		printf("삭제할 노드가 존재하지않습니다\n");
		return;
	}
	else {
		HEAP_NODE* delNode = heap->tr[1];
		heap->tr[1] = heap->tr[heap->n];
		heap->n--;
		
		heap->pos[heap->tr[1]->node] = 1;
		heap->pos[delNode->node] = 0;
		int idx = 1;
		while (idx * 2 <= heap->n && heap->tr[idx * 2]->distance < heap->tr[idx]->distance) {
			int child = idx * 2;
			if (heap->tr[child]->distance > heap->tr[child + 1]->distance) {
				child++;
			}
			swap_node(heap, heap->tr[child], heap->tr[idx]);
			HEAP_NODE* temp = heap->tr[child];
			heap->tr[child] = heap->tr[idx];
			heap->tr[idx] = temp;

			idx = child;
		}


		return delNode;
	}
}

void Update_Node(HEAP_TREE* heap, int node, int distance) {
	//해당 노드 번호를 업뎃한다
	int idx = heap->pos[node]; //해당 노드의 트리에서의 위치
	heap->tr[idx]->distance = distance;

	//위로 올라가야 하는 경우
	if (idx !=1 && heap->tr[idx / 2]->distance > heap->tr[idx]->distance) {
		while (idx != 1 && heap->tr[idx / 2]->distance > heap->tr[idx]->distance) {
			swap_node(heap, heap->tr[idx / 2], heap->tr[idx]);
			HEAP_NODE* temp = heap->tr[idx / 2];
			heap->tr[idx / 2] = heap->tr[idx];
			heap->tr[idx] = temp;

			idx /= 2;

		}
	//아래로 내려가야 하는 경우
	}
	else if (idx*2 <=heap->n && heap->tr[idx * 2]->distance < heap->tr[idx]->distance) {
		while (idx * 2 <= heap->n && heap->tr[idx * 2]->distance < heap->tr[idx]->distance) {
			int child = idx * 2;
			if (heap->tr[child]->distance > heap->tr[child + 1]->distance) {
				child++;
			}
			swap_node(heap, heap->tr[idx], heap->tr[child]);
			HEAP_NODE* temp = heap->tr[idx];
			heap->tr[idx] = heap->tr[child];
			heap->tr[child] = temp;

			idx = child;
		}
	}
}

void dijkstra(int(*graph)[VERTEX_SIZE], int start, HEAP_TREE * heap, int * distance) {
	
	//초기단계
	HEAP_NODE* node = (HEAP_NODE*)calloc(1, sizeof(HEAP_NODE));
	assert(node != NULL);
	node->node = start;
	node->distance = 0;

	for (int i = 0; i < VERTEX_SIZE; i++) {
		if (i != start) {
			distance[i] = INF;
		}
	}
	distance[start] = 0;

	Insert_Node(heap, node);


	for(int i=0;i<VERTEX_SIZE;i++){
		HEAP_NODE* nowNode = Delete_Node(heap);
		//방문하고 있는 노드의 번호와 가중치
		int now = nowNode->node;
		int value = nowNode->distance;

		for (int i = 0; i < VERTEX_SIZE; i++) {
			
			if (distance[now] + graph[now][i] < distance[i]) {
				int IsInf = distance[i];
				distance[i] = distance[now] + graph[now][i];
				if (IsInf != INF) { 
					Update_Node(heap, i, distance[i]);
				}
				else {
					HEAP_NODE* node = (HEAP_NODE*)calloc(1, sizeof(HEAP_NODE));
					assert(node != NULL);
					node->node = i;
					node->distance = distance[i];
					Insert_Node(heap, node);
				}
			}
		}
		
		printf("\nSTEP %d : distance => ", i+1);
		for (int i = 0; i < VERTEX_SIZE; i++) {
			if (distance[i] == INF) {
				printf("*  ");
			}
			else {
				printf("%d ", distance[i]);
			}
			
		}
	}

}

int main() {

	int graph[VERTEX_SIZE][VERTEX_SIZE] = { {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} };

	HEAP_TREE* heap = (HEAP_TREE*)calloc(1, sizeof(HEAP_TREE));
	assert(heap != NULL);

	int distance[VERTEX_SIZE];
	
	for (int i = 0; i < VERTEX_SIZE; i++) {
		
		printf("\n\n[START: %d]", i);
		dijkstra(graph, i, heap, distance);
	}




	getchar();
	return 0;
}

cf> 공부하면서 알게된 것

: 원래 distance 배열을 초기화할 때 memset함수를 통해 memset(distance, INF, sizeof(distance))를 했는데 제대로 초기화되지 않았다. 알아보니, 0이 아닌 int 타입의 숫자를 넣게 되면 예상할 수 없는 값으로 세팅된다

=> memset함수는 1byte 단위로 값을 초기화 하기 때문에 만약 1로 초기화한다면 1byte단위로 1를 만들기 때문에 4byte로 표현된 int 숫자 1은 제대로된 숫자로 표현될 수 없다

(0은 4byte든 1byte든 0이기때문에 상관없음)

=> 결론 : 0과 char 타입만 사용하자! 

 

++보완 코드 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <memory.h>

#define INF 100000
#define MAX_HEAP_SIZE 100
#define NODE_COUNT 7
int pos[NODE_COUNT - 1];



typedef struct _HEAP_NODE_ {
	int vertex;
	int distance;
}HEAP_NODE;

typedef struct HEAP_TREE {
	int n;
	HEAP_NODE* heap[MAX_HEAP_SIZE];
}HEAP_TREE;

void init(int start, int* distance, bool* visited, HEAP_TREE* tr) {
	memset(pos, 0, sizeof(pos));
	for (int i = 0; i < NODE_COUNT; i++) {
		if (i == start) {
			distance[i] = 0;
		}
		else {
			distance[i] = INF;
		}
	}
	memset(visited, 0, sizeof(visited));
	tr = (HEAP_TREE*)calloc(1, sizeof(HEAP_TREE));
	assert(tr != NULL);
}


void change(HEAP_NODE** x, HEAP_NODE** y) {
	int temp = pos[(*x)->vertex];
	pos[(*x)->vertex] = pos[(*y)->vertex];
	pos[(*y)->vertex] = temp;

	HEAP_NODE* tempNode = *x;
	*x = *y;
	*y = tempNode;
}

void insertHeapNode(HEAP_TREE* tr, int vertex, int distance) {
	HEAP_NODE* newNode = (HEAP_NODE*)calloc(1, sizeof(HEAP_NODE));
	assert(newNode != NULL);
	newNode->vertex = vertex;
	newNode->distance = distance;
	tr->heap[++(tr->n)] = newNode;
	pos[vertex] = tr->n;
	int idx = tr->n;
	while (idx != 1 && tr->heap[idx / 2]->distance > tr->heap[idx]->distance) {
		change(&(tr->heap[idx]), &(tr->heap[idx / 2]));
		idx /= 2;
	}
}

void updateHeapNode(HEAP_TREE* tr, int vertex, int distance) {
	int posOfVertex = pos[vertex];
	HEAP_NODE* this = tr->heap[posOfVertex];
	bool down = false;
	if (this->distance < distance) {
		//distance값이 더 커진다면 내려가야함
		down = true;
	}
	this->distance = distance;
	int idx = posOfVertex;
	if (down == false) {
		//올라가야함
		while (idx != 1 && tr->heap[idx / 2]->distance > tr->heap[idx]->distance) {
			change(&(tr->heap[idx]), &(tr->heap[idx / 2]));
			idx /= 2;
		}
	}
	else {
		while (idx * 2 <= tr->n && tr->heap[idx * 2]->distance < tr->heap[idx]->distance) {
			int child = idx * 2;
			if (tr->heap[child]->distance > tr->heap[child + 1]->distance) {
				child++;
			}
			change(&(tr->heap[idx]), &(tr->heap[child]));
			idx = child;
		}
	}
	
}

HEAP_NODE* deleteHeapNode(HEAP_TREE* tr) {
	HEAP_NODE* delNode = tr->heap[1];
	pos[delNode->vertex] = 0;
	tr->heap[1] = tr->heap[tr->n];
	pos[tr->heap[1]->vertex] = 1;
	(tr->n)--;
	int idx = 1;
	while(idx*2<=tr->n && tr->heap[idx * 2]->distance < tr->heap[idx]->distance) {
		int child = idx * 2;
		if (tr->heap[child]->distance > tr->heap[child + 1]->distance) {
			child++;
		}
		change(&(tr->heap[idx]), &(tr->heap[child]));
		idx = child;
	}

	return delNode;
}



void dijkstra(int(*graph)[NODE_COUNT], int start,int * distance, bool * visited, HEAP_TREE * tr) {

	//init
	insertHeapNode(tr, start, 0);

	for (int i = 0; i < NODE_COUNT ; i++) {
		HEAP_NODE* now = deleteHeapNode(tr);
		visited[now->vertex] = true;
		for (int j = 0; j < NODE_COUNT; j++) {
			if (distance[now->vertex] + graph[now->vertex][j] < distance[j]) {

				int item = distance[now->vertex] + graph[now->vertex][j];
				
				if (distance[j] == INF) {
					insertHeapNode(tr, j, item);

				}
				else {
					updateHeapNode(tr, j, item);
				}
				distance[j] = item;
			}
			
		}
		printf("\nSTEP %d : distance => ", i + 1);
		for (int i = 0; i < NODE_COUNT; i++) {
			if (distance[i] == INF) {
				printf("* ");
			}
			else {
				printf("%d ", distance[i]);
			}
		}

	}
}


int main() {

	int graph[NODE_COUNT][NODE_COUNT] = { {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} };
	
	HEAP_TREE* tr = (HEAP_TREE*)calloc(1, sizeof(HEAP_TREE));
	assert(tr != NULL);
	int* distance = (int*)calloc(NODE_COUNT, sizeof(int));
	assert(distance != NULL);

	bool* visited = (bool*)calloc(NODE_COUNT, sizeof(bool));
	assert(visited != NULL);

	for (int i = 0; i < NODE_COUNT; i++) {
		printf("\n\n[Start Node : %d]\n", i);
		init(i, distance, visited, tr);
		dijkstra(graph, i, distance, visited, tr);
		
	}





	getchar();
	return 0;
}