STUDY/알고리즘

Dijkstra의 개념 및 구현

ME74 2019. 12. 16. 03:00

들어가며

오늘은 엄청 유명한 '다익스트라 알고리즘'에 대해 공부해 볼 예정이다.
그래프와 트리에 관한 알고리즘에 특히 약한 편이라 더더 열심히 해야할 것 같다.

개념 및 특징

  • 한 정점에서 나머지 모든 정점까지의 최단 경로를 찾는 알고리즘
  • 음수인 간선을 포함하는 경우 최단 경로를 찾을 수 없는 경우가 있음

구현

  • 연결되지 않은 정점들 간의 거리는 INF(무한대)로 표현

알고리즘

  1. 모든 정점을 미방문 상태로 표시한다.
  2. 모든 정점 간의 거리를 INF(무한대)로 표시한다.
  3. 이어진 정점 간의 거리를 표시한다.
  4. 현재 정점(초기값은 시작점)을 방문 상태로 표시한다.
  5. 현재 정점과 이어진 정점들에 대해 (시작점에서 현재 정점까지의 거리) + (현재 정점에서 이어진 정점까지 거리) < (시작점에서 이어진 정점까지 거리)을 만족하면 (시작점에서 이어진 정점까지 거리)를 (시작점에서 현재 정점까지의 거리) + (현재 정점에서 이어진 정점까지 거리)로 업데이트 시켜준다.
  6. 미방문 상태이면서 (시작점에서 정점까지의 거리)가 최소인 정점을 현재 정점으로 선택한다.
  7. 모든 노드가 방문상태가 될 때까지 4~6번의 과정을 반복한다.

소스코드(C++)

#include <iostream>

using namespace std;

#define MAX 100
#define INF 10000

int dijkstra[MAX][MAX];
int already[MAX];

int main(void)
{
	int Node, N, K; // Node: num of nodes, N: num of inputs, K: start Node
	cin >> Node >> N >> K;
	
	for(int i=1; i<=Node; ++i)
	 for(int j=1; j<=Node; ++j)
	 	if(i==j)
	 		dijkstra[i][j] = 0;
	 	else	
	 		dijkstra[i][j] = INF;
	
	int n1, n2, w;
	for(int i=0;i<N;++i) {
		cin >> n1 >> n2 >> w;
		dijkstra[n1][n2] = w;
		dijkstra[n2][n1] = w;
	}
	
	int pos = K;
	int min_v, min_i;
	do {
		min_v = -1;
		min_i = -1;
		already[pos] = 1;
		for(int i=1; i<=Node;++i) {
			if(dijkstra[K][i] > dijkstra[K][pos] + dijkstra[pos][i])
				dijkstra[K][i] = dijkstra[K][pos] + dijkstra[pos][i];
			if((min_v == -1 || min_v > dijkstra[K][i]) && !already[i]) {
				min_v = dijkstra[K][i];
				min_i = i;	
			}
		}
		pos = min_i; 
	} while(pos != -1);
	
	for(int i=1;i<=Node;++i) {
		for(int j=1;j<=Node;++j)
			cout << dijkstra[i][j] << ' ';
		cout << endl;	
	}
	
	return 0;
}

관련문제