ZDNet Korea…전산학「새 지평 연」다익스트라

데이크스트라 알고리즘에 대한 설명 가운데 그나마 수월한 편. MIT press의 Introduction to Algorithms에 나온 설명은 들여다 보기만 해도 안습이다. 그런데 내가 이 알고리즘을 제대로 이해하고 있기는 한 걸까? OTL

다익스트라의 대표적인 업적 중 하나인 최단경로 알고리즘은 한 정점에서 다른 모든 정점으로의 최단경로를 구하는 알고리즘이다. 최단경로와 최단거리를 모두 얻을 수 있는 이 알고리즘은 그동안 철도 건설과 통신 네트워크의 경로 설계, 항공기 운항 계획 등 목적지에 이르는 최선의 길을 찾아야 하는 응용 분야에서 사용됐다.

전산학에서는 다익스트라 알고리즘이 특히 네트워크 경로 설계에 많이 적용되는데 대표적인 예가 OSPF(Open Shortest Path First)라는 IP 망에서의 라우팅 프로토콜이다. 다익스트라 알고리즘은 다음과 같이 설명된다.

[1] 시작 정점에서 가장 인접한 정점을 찾는다. 그 정점까지 거리가 최단거리이다. 지금까지 최단거리가 알려진 정점은 2개(자기 자신과 지금 찾은 정점)가 된다. 최단거리가 알려진 정점들의 집합을 S라 하자.

[2] 집합 S에 포함되지 않은 정점 중에서 시작 정점으로부터 가장 가까운 정점을 찾는다. 이 새로운 정점은 집합 S에 바로 이웃한 정점들 중 하나일 것이다. 그 정점까지 거리는 최단거리이며, 그 정점을 집합 S에 포함시킨다.

[3] 새로운 정점이 없을 때까지, 즉 모든 정점이 집합 S에 포함될 때까지 []의 과정을 반복한다.

<그림 1> 다익스트라 알고리즘

다익스트라 알고리즘으로 <그림 1>과 같은 철도 노선에서 S부터 T까지의 최단경로를 구하는 과정은 다음과 같다.

[1] 초기의 집합은 시작 노드(S)만으로 구성된다.

[2] C3을 총 시간 비용 2를 가지고 집합에 추가한다.

[3] C2가 S→C3→C2 의 경로를 거쳐 총비용 4로 추가된다.

[4] C1이 총비용 5로 추가된다.

[5] 그렇게 하면 이 시점의 집합은 S, C1, C2, C3 로 구성된다.

[6] C4가 S→C1→C4 의 경로를 통해 11의 비용으로 추가된다.

[7] 마지막에는 T 가 S→C3→C2→T 의 경로를 통해 16의 비용으로 추가된다.

다익스트라 알고리즘이라 불리는 이 최단 경로 알고리즘은 발표된 1959년 이후로 일반적인 유/무향 그래프의 최단경로를 구하는 알고리즘 대부분의 기본이 됐다.