다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘 : 한 정점에서 다른 정점들로 가는 최단경로를 구하는 알고리즘 

<시간 복잡도>

그냥 기본적인 알고리즘은 노드를 선택할 때 계속 최단 거리의 노드를 찾아주어야 하기에 O(n^2) 시간복잡도가 걸린다.

그렇기에 넣을 때 logn시간이 걸리는 priority_queue를 사용하면 O(nlogn)시간 복잡도로 줄일 수 있다. 그렇기에 현재 코드는 priority_queue로 구현 하였다.

 

<전체적인 알고리즘>

1. 시작노드에서부터 해당 노드로의 최단 거리(배열에 저장된 거리) 중 가장 짧은 노드 선택.(전에 선택된 것들 제외)

2. 선택된 노드에서부터 다음 노드로 가는 경로가 배열에 저장된 최단 경로보다 작으면 갱신

3. 1-2를 끝날 때까지 반복

 

<경로 찾는 알고리즘>

1. 최단 거리가 갱신될 때마다 pre배열에 그 전 노드를 기록해둠.

2. 나중에 재귀 함수로 그 전 노드들을 계속 탐색하면 결국 시작노드까지의 경로가 발견됨.

 

 

<전체 코드>

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int n = 5;
vector<pair<int,int>> a[7];
int INF = 987654321;
int d[7];
int pre[7];


void dijkstra(int start)
{
	fill(&d[0], &d[7], INF);  //각 정점 거리 무한대로 셋팅
	
	priority_queue <pair<int, int>> pq;  //정점 중에 거리가 최소인 정점부터 갱신해야 하기 때문에
	pq.push(make_pair(0, start));

	d[start] = 0;

	while(!pq.empty())
	{
		int node = pq.top().second;
		int distance = -pq.top().first;  //거리에 -를 붙어야 최소인 거리부터 정렬됨
		pq.pop();

		if (distance > d[node])continue;  

		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i].first;
			int nextdistance = a[node][i].second + distance;
			if (nextdistance < d[next])  //현재 노드로 부터 가는 거리가 더 짧으면 갱신
			{
				d[next] = nextdistance;
				pre[next] = node;
				pq.push(make_pair(-nextdistance, next));
			}
		}
	}
}

void path(int node)  // 현재 노드의 전 노드를 확인하며 경로 찾기
{
	if (node != pre[node])path(pre[node]);
	
	printf("%d  ", node);
}

int main()
{
	for (int i = 1; i <= n; i++)
	{
		pre[i] = i;
	}

	a[1].push_back(make_pair(3,6));  //그래프 셋팅
	a[1].push_back(make_pair(4, 3));
	a[2].push_back(make_pair(1, 3));
	a[3].push_back(make_pair(4, 2));
	a[4].push_back(make_pair(2, 1));
	a[4].push_back(make_pair(3, 1));
	a[5].push_back(make_pair(2, 4));
	a[5].push_back(make_pair(4, 2));

	int start = 5;
	dijkstra(start);  //5에서 시작할 경우

	printf("시작노드는 %d\n\n", start);
	for (int i = 1; i <= n; i++)
	{
		printf("노드 %d로의 최단거리 : %d\n", i, d[i]);
	}
	cout << "\n";
	for (int i = 1; i <= 5; i++)
	{
		printf("노드 %d로 가는 최단 경로 : ",i);
		path(i);
		cout << "\n";
	}
	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.