다익스트라 알고리즘[Dijkstra Algorithm]

Shortest Path Problem 문제를 해결하기 위한 알고리즘

각 edge에 가중치를 두는 weighted Graph에서 사용

Connected Graph에서 사용

가중치가 음수가 없어야함. 

어떤 vertex를 시작점으로 하여 다음 vertex를 연결하는 edge의 가중치를 계산하여서

가장 작은 가중치를 가지는 경로를 탐색

가중치란 

평균치(平均値:평균값)를 산출할 때 각 개별치(個別値)에 부여되는 중요도.

그런데 상황마다 다를것이다.

예를 들어 가난한 사람과 부자인 사람을 생각해보자

부자인 사람은 시간이 더 가치있다고 생각 하기때문에 edge를 통과하는데 걸리는

시간이 작은것에 더 높은 가중치를 둘것이다.

하지만 가난한 대학생의 경우 시간은 많지만 돈이 없기때문에 edge를 통과하는데

소비되는 돈의 양을 줄이는데 더 높은 가중치를 둘것이다.

코드

출처[http://kaspyx.kr/64]

생각하면서 너무 많이 헷갈려서 초기화 값부터 조금씩 찾아갔다...

어렵다..

###############################################################

#include "stdio.h"
#include "stdlib.h"

#define INF 9999
#define N 5
void Dij();



//배열 생성
int Arr[N + 1][N + 1]
= {
	//A  B  C  D  E  F
	{ 0, 0, 0, 0, 0, 0 },//A
	{ 0, 0, 0, 0, 0, 0 },//B
	{ 0, 0, 0, 0, 0, 0 },//C
	{ 0, 0, 0, 0, 0, 0 },//D
	{ 0, 0, 0, 0, 0, 0 },//E
	{ 0, 0, 0, 0, 0, 0 } //F
};


int main()
{
	Dij();

	system("pause");
}
void Dij()
{	int index = 0;
	int index_2 = 0;
	int min = 0;
	int next_node = 0;

	//초기화
	for (index = 0; index < N + 1; index++)
	{
		for (index_2 = 0; index_2 < N + 1; index_2++)
		{
			Arr[index][index_2] = INF;
		}
	}

	//연결된 방향 노드 설정
	Arr[0][1] = 20; //a -> b
	Arr[0][3] = 30; //a -> d
	Arr[1][2] = 20; //b -> c
	Arr[1][4] = 40; //b -> e
	Arr[2][5] = 20; //c -> f
	Arr[3][2] = 20; //d -> c
	Arr[3][5] = 30; //d -> f
	Arr[4][5] = 10; //e -> f
	Arr[3][4] = 20; //d -> e
	///////////////////////////////////////////////////////
	//D[Vi] 시적점 v1부터 꼭짓점 Vi까지의 최단 경로
	//a를 시작점이면 
	//a를 시작점으로 하여서 각 꼭짓점까지의 최단경로
	//Distance 초기 vertex부터 Vn[a...f]까지 최단 경로
	int Distance[N + 1] = { 0 };

	for (index = 1; index < N + 1; index++)
	{
		Distance[index] = INF;
	}
	//이미 방문한 정점들을 표시함
	//그리고 최근 경신된 정점에서 다시 다음 정점 거리를 계산한다.
	int Visit[N + 1] = { 0 };

	//가장 가까운 점을 표현하는ㄷ ㅔ사용
	int Shortest_Node = 0;

	for (index = 1; index < N + 1; index++)
	{
		//최솟값을 찾기위한 초기화
		min = INF;

		for (index_2 = 0; index_2 < N + 1; index_2++)
		{
			//1. 먼저 방문하지 않은 노트을 선택
			//2. 가장 가까운 노드를 선택한다.

			//D[1] = D[0] + 0->1 20
			//D[2] = D[0] + 0->2 INF
			//D[3] = D[0] + 0->3 30
			//D[4] = D[0] + 0->4 INF
			//D[5] = D[0] + 0->5 INF
			//여기서 가장 짧은 놈을 선택
			if (Visit[index_2] == 0 // 방문하지 않는 노드를 확인
				&& min > Distance[index_2]
				)
			{
				min = Distance[index_2];
				Shortest_Node = index_2;
			}
		}

		//가장 가까운 정점을 방문했다는 표시를 함.
		Visit[Shortest_Node] = 1;

		//현재 머물고 있는 Node가 Shortest Node임
		//해당 반복문에서는 다음 거리까지의 총 거리를 구하는 역할임.
		//D[1] = D[0] + 0->1 20
		//D[2] = D[0] + 0->2 INF
		//D[3] = D[0] + 0->3 30
		//D[4] = D[0] + 0->4 INF
		//D[5] = D[0] + 0->5 INF
		////////////////////////////
		//1이선택 [B]
		//D[0] 0 > D[1] 20 + 1->0 INF
		//D[1] 20 =  D[1] 20 + 1->1 0 
		//D[2] INF  D[1] 20  + 1->2 40
		for (index_2 = 1; index_2 < N + 1; index_2++)
		{
			if (Distance[index_2] > Distance[Shortest_Node] + Arr[Shortest_Node][index_2])
			{
				Distance[index_2] = Distance[Shortest_Node] + Arr[Shortest_Node][index_2];
			}
		}
	}
	printf("%d \n", Distance[5]);
}