[CS] 다익스트라 알고리즘

/* 다익스트라 알고리즘 */

다익스트라(dijkstra) 알고리즘은 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다. 

해당 과정에서 도착 노드뿐만아니라 모든 다른 노드까지의 최단 경로로 방문하며 각 노드까지의 최단 경로를 찾게 된다.

매번 최단 경로의 노드를 선택해 탐색을 반복하는 것이다.

 

/* 동작 원리 */

1. 시작 노드와 끝 노드를 설정한다.
2. 테이블을 초기화한다.
3. 노드의 인접 노드 (adjacent nodes) 중 방문하지 않은 노드를 구별하고, 그 중 가장 짧은 노드를 선택하고 방문처리 한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 edge 를 계산해 테이블을 업데이트한다.

/* 예시 */

 

출발 노드 1번, 도착 노드 6번 설정.

테이블은 inf로 초기화

edge도 표기함

 

 

 

출발 노드는 거리가 0이다.

 

1번의 인접 노드는 2,4 이다. 그곡까지 가는 거리를 각각 기존의 값과 비교해 최솟값으로 업데이트 한다.

그 후 1번 노드는 방문 표시를 한다. 방문하지 않는 노드 중 가장 작은 값을 가진 4번 노드를 다음 노드를 선택한다.

 

4번 노드의 인접 노드는 1, 2, 5이다. 1번은 직전에 방문을 했으므로 볼 필요가 없다.

5번의 경우 - (1->4->5) 와 기존의 값인 inf 중 최솟값을 넣는다

2번의 경우 - (1->4->2) 와 기존의 값인 2 중 최솟값을 넣는다.

다음으로 선택될 노드는 아직 방문하지 않은 노드 중 가장 작은 값을 가진 2 또는 5이다. 2로 가보자

 

 

2번의 인접노드인 3과 4번 노드에 대해 같은 과정을 반복한다.

그 다음으로 5번으로 가보자

 

 

5번 노드와 연결된 6번 노드에 같은 과정을 반복한다.

다음 노드를 선택해야 하는데 아직 방문하지 않은 3번과 6번 중 거리값이 작은 것은 6이다. 그런데 6번은 도착 노드이므로 알고리즘을 종료한다.

 

 

결과적으로 1번노드에서 6번까지 오는 데의 최소 거리는 4가 된다.

 

/* 특징 */

다익스트라 알고리즘은 edge 값이 양수 일때만 사용 가능하다.

 

구현하는 방법은 두가지이다.

방문하지 않은 노드를 다루는 방식에서 '순차 탐색' 혹은 '우선수위 큐' 를 사용할 수 있다.