다익스트라 알고리즘 분석

1. 이론적 기초

다익스트라 알고리즘(이하 DJ 알고리즘)의 이론적 기초는 하나의 간단한 정리입니다:

다음 최단 경로는 호(V0, Vx)이거나, S에 속한 일부 정점을 거쳐 Vx에 도달하는 경로입니다. (S는 최단 경로가 이미 알려진 정점들의 집합입니다)

(정리를 정확하게 설명하기 위해 원문을 그대로 발췌했습니다. 정리가 맞는지에 대해서는 귀류법으로 증명 가능하다고 합니다.) 명백히 이것은 점진적 알고리즘입니다. 다음 경로가 없을 때까지 반복적으로 다음 최단 경로를 구합니다.

2. 문제 분석

다음과 같은 가중치 방향 그래프가 있습니다:

V0에서 출발하여 다른 모든 정점에 도달하는 최단 경로를 구합니다.

먼저 설명을 쉽게 하기 위해 수학적 형식으로 변환해야 하며, 이에 대응하는 인접 행렬을 작성합니다(x는 도달 불가능을 의미함):

0	50	10	x	45	x
x	0	15	x	10	x
20	x	0	15	x	x
x	20	x	0	35	x
x	x	x	30	0	x
x	x	x	3	x	0

정리를 분석하면 다음과 같은 결론을 얻을 수 있습니다. 현재 S 집합에는 정점 V0 하나만 있습니다(V0에서 자신으로 가는 경로는 확실히 최단 경로입니다). 보조 공간인 S 집합 외에도 다음이 필요합니다:

• V 집합: 최단 경로를 아직 모르는 정점들로 구성된 집합, 즉 S 집합의 여집합
• path[]: 최단 경로를 기록하여 결과를 표시하는 데 사용
• dist[]: 경로 길이를 기록하며 위와 동일한 역할 수행
• Vx: 다음 정점을 기록

준비가 끝났으니 풀이를 시작할 수 있습니다.

3. 풀이 과정

0. 초기 상태

dist[]는 V0에서 각 정점까지의 직접 거리(x는 직접 연결되지 않음을 의미)로 초기화하고, path[]는 대응하는 경로로 초기화합니다. 직접 연결되지 않은 경우 NULL로 표시합니다. V 집합 중 dist 값이 가장 작은 정점 V2를 다음 정점(정리에서의 Vx)으로 선택합니다.

1. 1단계

V2를 S 집합에 추가하면 V2라는 경유지가 생깁니다. 다음으로 dist[]를 업데이트하여 V2를 거쳐 가는 것이 더 짧은지 확인합니다. 계산 결과에 따라 dist[]와 path[]를 업데이트하고, 더 짧은 경로 길이와 해당 경로를 저장합니다. V 집합 중 dist 값이 가장 작은 V3를 다음 정점으로 선택합니다.

2. 2-5단계

V 집합에 선택할 정점이 없을 때까지 다음 정점을 계속 선택합니다.

4. 요약

DJ 알고리즘의 과정은 매우 간단합니다:

1. S의 첫 번째 정점(즉, 출발점 V0)을 확정합니다.
2. 정리에 따라 점진적으로 계산합니다(계속해서 최단 경로를 찾고, 해당 최단 경로를 경유지로 활용해 봅니다).

알고리즘의 개념 자체는 어렵지 않습니다. 처음에 이해하지 못했던 이유는 구체적인 의사코드 구현 방식에 얽매였기 때문입니다. 따라서 알고리즘을 공부할 때는 구현보다는 개념에 집중해야 합니다. 특히 의사코드는 보조 공간이 왜 필요한지 설명하지 않은 채 생소한 데이터 구조를 임의로 선언하곤 합니다. 예를 들어 이번 사례에서 S 집합과 V 집합은 하나만 있어도 충분하며, path[]와 dist[] 역시 구조체로 깔끔하게 표현할 수 있습니다. 하지만 의사코드에서는 이 모든 것을 산발적으로 사용하여, 과도한 보조 공간이 오히려 알고리즘 자체를 이해하는 데 방해가 되기도 합니다.