다익스트라 알고리즘

정의

다익스트라 알고리즘은 한 출발 노드에서 나머지 모든 노드까지의 최단경로를 구한다.

대상은 가중치 그래프이고, 탐색은 그리디 방식으로 진행된다.

모든 쌍의 최단경로를 구하는 플로이드 방식과는 구분해 두어야 한다.

그리디 원리와 탐색 절차

먼저 출발 노드의 거리는 0, 나머지 노드의 거리는 무한대로 둔다.

아직 확정되지 않은 노드 중 잠정 거리가 가장 작은 노드를 고른다.

그 노드를 확정하고 이웃 노드마다 완화를 수행해 더 짧은 거리로 갱신한다.

모든 노드가 확정될 때까지 반복하고, 선행 노드를 따라 경로를 되짚는다.

확정된 거리는 이후 바뀌지 않는다. 이것이 그리디 원리다.

예시 계산

예시 도로망은 노드 네 개이고 출발 노드는 A다. 링크 값은 통행시간(분)이다.

A에서 C는 2분, B는 4분이다. 가장 작은 C를 먼저 확정한다.

C를 거치면 B는 2+1=3분으로 줄고, D는 10분이 된다.

이제 B를 확정한다. 그다음 B를 거쳐 D로 가는 비용을 구해 보자.

B를 거치면 D는 8분이 된다. 앞서 10분이던 값을 8분으로 낮춘다.

남은 D를 확정하면 모든 노드가 정해진다. 최단경로는 A→C→B→D, 8분이다.

비교와 한계

다익스트라는 단일 출발점 문제를 그리디로 푸는 대표 기법이다.

벨만-포드는 음수 가중치를 다루지만 계산량이 크다.

플로이드-워셜은 모든 노드 쌍의 거리표가 필요할 때 쓴다.

다익스트라는 음수 가중치와 혼잡을 반영하지 못하는 한계가 있다.

통행배정에서는 링크 통행시간이 음수가 아니므로 다익스트라가 기본이다.

핵심 정리

이제 핵심을 정리한다. 정의와 조건부터 확인한다.

정의는 한 출발 노드에서 모든 노드까지의 최단경로를 구하는 그리디 알고리즘이다.

조건은 모든 링크 비용이 0 이상이어야 한다는 점이다. 원리는 최소 노드 확정이다.

활용은 통행배정의 OD 최단경로이고, 한계는 음수 비용과 혼잡이다.