다익스트라 알고리즘

다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다.

다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요하겠지만, 일단은 간단하게 구성해보았습니다.  (참조 : http://sdev.tistory.com/72 , http://sdev.tistory.com/71)

이 소스는 애시당초 프림 알고리즘 소스를 만들었던 것을 고친지라, 코멘트가 프림에 맞추어져 있습니다.

// Dijkstra.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#define	NIL			(0)

///	인접리스트를 위한 구조체 선언
struct vlist
{
	int vertex;
	int weight;
	vlist *next;
};

///	정점 v에 w라는 가중치를 갖는 정점 추가
void Add(vlist **list, int v, int w)
{
	vlist *p = new vlist;
	p->vertex = v;
	p->weight = w;
	p->next = *list;
	*list = p;
}

int _tmain(int argc, _TCHAR* argv[])
{
	vlist *list[8];	//	인접리스트 선언
	for( int i = 0 ; i < 8 ; i++ ) list[i] = NIL;
	//	인접리스트 추가
	Add(&list[0], 1, 8);	///	0->1 (8)
	Add(&list[0], 5, 9);
	Add(&list[0], 4, 11);
	Add(&list[1], 2, 10);
	Add(&list[2], 3, 2);
	Add(&list[3], 7, 4);
	Add(&list[4], 6, 8);
	Add(&list[4], 7, 8);
	Add(&list[5], 2, 1);
	Add(&list[5], 1, 6);
	Add(&list[5], 4, 3);
	Add(&list[6], 3, 5);
	Add(&list[6], 5, 12);
	Add(&list[7], 6, 7);

	int d[8];			//	정점값
	int v[8];			//	프림집합에 속했는가?
	int n = 0;			//	프림집합의 원소 갯수
	int prev[8];		//	정점값이 오게된 정점

	//	정점의 값을 모두 무한대로 설정
	for( int i = 0 ; i < 8 ; i++ )
		d[i] = 1000;

	//	프림집합을 공집합으로 설정
	for( int i = 0 ; i < 8 ; i++ )
		v[i] = 0;

	//	시작정점값을 0으로 설정
	d[0] = 0;

	//	프림집합이 전체집합이 아닌동안
	//	while( S != V )
	while( n != 8 )
	{
		//	최소정점값을 가지는 정점 선택
		//	u <- extractMin(V-S, d)
		int u, min = 1000;
		for( int i = 0 ; i < 8 ; i++ )
			if( v[i] == 0 && d[i] < min )
			{
				u = i;
				min = d[i];
			}

		//	선택된 정점을 프림집합에 넣는다.
		//	S = S ∪ { u }
		v[u] = 1;
		n++;
		
		//	선택된 정점에 인접한 모든 정점에 대하여
		//	for each v ∈ L(u)
		vlist *t = list[u];
		while( t != NIL )
		{
			int v1 = t->vertex;
			//	v 가 현재 프림집합에 속해있지 않고,
			//	w(u, v)가 v의 정점값보다 작으면
			//	if v ∈ V - S and d[u]+w(u, v) < d[v] then
			if( v[v1] == 0 && d[u]+t->weight < d[v1] )
			{
				d[v1] = d[u]+t->weight;
				prev[v1] = u;
			}
			t = t->next;
		}
	}

	//	계산된 결과를 출력
	for( int i = 1 ; i < 8 ; i++ )
		printf("%d(%d)\n", d[i], prev[i]);

	return 0;
}