다익스트라 알고리즘

 

 

✔️ 다익스트라 최단 경로 알고리즘 개요 :

 

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산

음의 간선이 없을 때 정상적으로 동작 (현실 세계와 유사)

그리디 알고리즘으로 분류 (매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복)

 

✔️ 동작 방법

 

1. 출발 노드 설정

2. 출발 노드 기준으로 각 노드의 최소 비용 저장

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 후 방문 노드로 설정

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

5. 3~4번 반복

 

 

[문제]

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

방법 1. 2차원 배열을 사용하여 그래프 저장 (메모리 초과)

#include <iostream>

using namespace std;

#define INF 2e9

int map[20001][20001];
int dst[20001];
int visit[20001];
int V, E;


int find_smallest(){

	int MIN = INF;
	int index = -1;
	for(int i = 1; i<= V; i++)
	{
		if(visit[i])
			continue;
		if(dst[i] < MIN) {
			MIN = dst[i];
			index = i;
		}
	}
	return index;
}

void dijkstra(int startNum)
{
	int next;
	dst[startNum] = 0;
	visit[startNum] = 1;

	for(int i = 1; i <= V; i++)
	{
		if (map[startNum][i] != 0)
			dst[i] = map[startNum][i];
	}

	while(1)
	{
		next = find_smallest();
		if (next == -1)
			break;
		visit[next] = 1;

		for(int i = 1; i <= V; i++)
		{
			if (map[next][i] != 0 && map[next][i] + dst[next] < dst[i])
				dst[i] = map[next][i] + dst[next];
		}
	}
}

int main() {

	int startNum;
	int u, v, w;
	cin >> V >> E;

	cin >> startNum;

	for(int i = 1; i <= E; i++)
	{
		cin >> u >> v >> w;
		if (!map[u][v])
			map[u][v] = w;
		else
		{
			if (map[u][v] > w)
				map[u][v] = w;
		}
	}
	for(int i = 1; i <= V; i++)
		dst[i] = INF;

	dijkstra(startNum);

	for(int i = 1; i <= V; i++)
	{
		if (dst[i] == INF)
			cout << "INF" << endl;
		else
			cout << dst[i] << endl;
	}
	return 0;
}

주어진 메모리 조건을 초과한다.

 

 

 

방법2. 그래프를 vector로 표현하는 방법 (시간 초과)

#include <iostream>
#include <vector>

#define INF 2e9

using namespace std;

vector<pair<int, int>>map[20001];
int dst[20001];
int visit[20001];
int V, E;

int find_smallest(){

	int MIN = INF;
	int index = -1;
	for(int i = 1; i<= V; i++)
	{
		if(visit[i])
			continue;
		if(dst[i] < MIN) {
			MIN = dst[i];
			index = i;
		}
	}
	return index;
}

void dijkstra(int startNum)
{
	int next;
	dst[startNum] = 0;
	visit[startNum] = 1;

	for(int i = 0; i < map[startNum].size(); i++)
	{
		dst[map[startNum][i].first] = map[startNum][i].second;
	} // 여기에서 그 loop을 쓸 수 있는지?

	while(1)
	{
		next = find_smallest();
		if (next == -1) {
			//cout << "out!" <<endl;
			break;
		}
		visit[next] = 1;

		for(int i = 0; i < map[next].size(); i++)
		{
			if (dst[map[next][i].first] > map[next][i].second + dst[next])
				dst[map[next][i].first] = map[next][i].second + dst[next];
		}
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int startNum;
	int u, v, w;
	cin >> V >> E;

	cin >> startNum;

	for(int i = 1; i <= E; i++)
	{
		cin >> u >> v >> w;
		map[u].push_back(make_pair(v, w));
	}

	for(int i = 1; i <= V; i++)
		dst[i] = INF;

	dijkstra(startNum);

	for(int i = 1; i <= V; i++)
	{
		if (dst[i] == INF)
			cout << "INF" << endl;
		else
			cout << dst[i] << endl;
	}

	return 0;
}

 

 

방법3. 우선순위 큐를 사용하는 방법 (OK)

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

#define INF 2e9

using namespace std;

vector<pair<int, int>>map[20001];
int dst[20001];
//int visit[20001];
int V, E;
priority_queue<pair<int, int>> PQ;

/*
int find_smallest(){

	int MIN = INF;
	int index = -1;
	for(int i = 1; i<= V; i++)
	{
		if(visit[i])
			continue;
		if(dst[i] < MIN) {
			MIN = dst[i];
			index = i;
		}
	}
	return index;
}
*/

void dijkstra(int startNum)
{
	int next;
	int distance;
	dst[startNum] = 0;

	PQ.push({0, startNum});

	while(!PQ.empty())
	{
		distance = - PQ.top().first;
		next = PQ.top().second;
		PQ.pop();

		for (int i = 0; i < map[next].size(); i++)
		{
			if (dst[map[next][i].first] > map[next][i].second + distance) {
				dst[map[next][i].first] = map[next][i].second + distance;
				PQ.push({-dst[map[next][i].first], map[next][i].first});
			}
		}
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);


	int startNum;
	int u, v, w;
	cin >> V >> E;

	cin >> startNum;

	for(int i = 1; i <= E; i++)
	{
		cin >> u >> v >> w;
		map[u].push_back(make_pair(v, w));
	}

	for(int i = 1; i <= V; i++)
		dst[i] = INF;

	dijkstra(startNum);

	for(int i = 1; i <= V; i++)
	{
		if (dst[i] == INF)
			cout << "INF" << endl;
		else
			cout << dst[i] << endl;
	}

	return 0;
}

 

값을 음수화하여서 최소힙으로 만들었다.

백준에서

ios_base::sync_with_stdio(0);
cin.tie(0);

를 넣어줘야만 시간 초과가 안난다.

자세한 내용은

https://nextcoder.tistory.com/10

ios_base::sync_with_stdio(false); cin.tie(NULL);

 

 

 

 

 

 

참고 사이트

 

https://m.blog.naver.com/ndb796/221234424646

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