본문 바로가기
Programming/Algorithm

다익스트라 알고리즘

by 작은별하나 2014. 10. 18.
반응형

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


다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요하겠지만, 일단은 간단하게 구성해보았습니다.  (참조 : 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;
}


댓글