[CS] 데이크스트라 알고리즘(Dijkstra algorithm) 분석

1. 개요

데이크스트라 알고리즘은 네덜란드의 컴퓨터 과학자인 에츠허르 데이크스트라가 1956년에 고안했으며 3년 뒤에 발표한 알고리즘입니다.

 

데이크스트라가 언론에서 밝힌 인터뷰에 의하면 해당 알고리즘은 ‘20분짜리 발명품’으로 약혼녀와 쇼핑 후 지친 상태에서 고안해냈다고 합니다. 이러한 20분짜리 발명품으로 데이스크라는 1972년 프로그래밍 언어 분야로 튜링상을 받기도 했습니다.

 

데이크스트라 알고리즘은 꼭짓점과 각 꼭짓점을 연결하는 변이 있는 그래프에서 두 꼭짓점간의 가장 짧은 경로를 찾는 알고리즘으로 우선순위 큐(Priority Queue)를 사용하지 않았기 때문에 시간복잡도는 𝑶(𝑉²) 입니다. 현재까지 다양한 변형을 통해 이용되고 있으며, 일반적으로는 그래프의 꼭짓점 중 특정 꼭짓점를 기준으로 다른 모든 꼭짓점과의 최단 거리를 찾는 알고리즘으로 변형하여 네트워크 라우팅 프로토콜 등에 주로 사용됩니다.

 

큐(Queue)와 우선순위 큐(Priority Queue)의 의미
큐는 First In First Out(선입선출) 방식의 자료구조로 프로세스에 CPU 자원을 할당할 때 이용되는 것을 대표적인 예시로 들 수 있습니다. 일반적인 큐의 경우 조건 없이 먼저 들어온 데이터가 먼저나가는 구조입니다. 하지만 이와 달리 우선순위 큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 구조로 되어있다는 점에서 차이가 있습니다.

 

시간복잡도와 𝑶(𝑉²)의 의미
시간복잡도는 ‘문제 해결에 결리는 시간과 입력의 함수관계’ 를 뜻하며, 어떤 알고리즘의 로직이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는데 사용됩니다. 이러한 특징을 이용해 프로그래밍 코드를 조금 더 효율적인 코드로 개선하기 위한 척도로 많이 사용됩니다. 보편적으로 빅오(𝑶) 표기법을 사용하여 표기하며, 그 중 𝑶(1), 𝑶(log 𝙣), 𝑶(𝙣) 등이 많이 사용됩니다. 그리고 시간복잡도 𝑶(𝑉²)의 𝑉는 Vertex(꼭짓점)를 의미하며, 이는 꼭지점 개수의 제곱만큼 시간복잡도가 발생되는 것을 뜻합니다. 이러한 시간복잡도는 ‘상대적으로 상당히 느리다.’ 라고 표현할 수 있습니다.

 

 

 

2. 분석

데이크스트라 알고리즘은 변(edge)에 양수의 값(가중치)을 부여한 가중 그래프(weighted graph)로 고안되었습니다.

 

참조 : 위키백과 - 가중그래프

 

가중 그래프 구조를 통해 우리는 데이크스트라 알고리즘이 ‘꼭짓점과 꼭짓점을 잇는 변의 가중치를 통해 최단 경로를 찾아내는 알고리즘’이라고 간단하게 정의 내릴 수 있습니다. 

 

위와 같은 정의를 바탕으로 데이크스트라 알고리즘을 코드와 유사하게 나타낼 경우 아래 이미지와 같습니다.

 

이미지 참조 : 한국방송통신대학교 - 이산수학 강의

 

 

---

사실 저는 위와 같은 자료 조사 및 강의 학습이 있었음에도 불구하고 데이크스트라 알고리즘의 절차를 이해가 쉽지 않았습니다. 하여 조금 더 자세한 이해를 위해 데이크스트라 알고리즘을 예시에 대입해서 분석해보았습니다.

 

 

‘도시’는 꼭짓점, ‘도시와 도시간의 항공편’은 변, 그리고 ‘항공편의 시간’을 가중치로 지정하고 예를 들어 보겠습니다.

유럽의 도시간 이동시 우리는 항공편의 소요시간을 고려하지 않을 수 없습니다. 그렇다면 소요시간을 위해 도시간의 직항이 가장 좋은 선택이겠죠. 하지만 여러가지 상황(비용,정책 등)으로 인해 직항을 탈 수 없는 경우도 많습니다. 이러한 상황을 가정하여 ‘항공편 환승을 통해 스페인에서 카자흐스탄으로 가기 위한 최소 소요시간 구하기’ 라는 문제를 예시로 만들어 보았습니다.

 

 

 

이미지 참조 : GREENBLOG (참고자료에 링크 첨부)

 

 

사전에 설명드린 여러가지 제약사항들로 직항을 이용할 수 없어 환승이 필요한 상황을 연출하기 위해 유럽 지도에 그래프를 표시해보았습니다. 그래프는 환승을 위한 도시(꼭짓점)와 각 도시간 항공편(변)의 시간(h,가중치)을 가정 후 구성했으며, 이를 통해 최소 소요시간을 계산해보겠습니다.

 

 

---

 

 

우선 데이크스트라 알고리즘을 예시에 대입할 경우 만들어지는 조건 및 절차는 아래와 같습니다.

 

(1) 시작 지점을 ‘a’,  소요시간을 ‘d’,  소요시간을 계산할 도시를 ‘u’,
     방문해야할 도시의 집합을 ‘Q’,  모든 도시의 집합을 ‘V’라고 지정한다.

(2) 계산을 위해 집합 V를 집합 Q에 대입한다. 시작 지점 초기 소요시간 d는 0으로 대입한다.

(3) 방문해야할 도시가 있는지에 대한 유무를 확인하기 위해 집합 Q를 탐색한다.
      탐색 결과 집합 V를 통해 대입된 도시들이 집합 Q 내부에 존재함으로 절차는 그대로 수행된다.

(4) 시작 지점 a에서부터 가장 소요시간이 짧은 도시를 선택하고, 방문해야할 도시의 집합 Q에서 해당 도시명을 제거한다.

(5) '(4)'에서 선택한 도시와 연결된 도시 중 집합 Q 내부에 남아있는 도시만을 u로 지정하고,
      시작 지점 a에서부터 u까지의 소요시간을 구한다.

(6) 다시 집합 Q를 탐색해서 내부에 도시명이 남아 있을 경우 ‘(4),(5)’ 조건을 수행한다.

(7) 위 절차를 반복 후 집합 Q 내부에 도시명이 존재하지 않을 시 계산은 종료된다.

 

 

위와 같은 조건들을 통해 만들어지는 예시의 상세한 절차는 아래와 같습니다.

 

 

집합 V에는 { 스페인, 영국, 그리스, 벨라루스, 스웨덴, 가자흐스탄} 존재하며, 집합 Q에 'V{도시}'를 대입합니다.
그리고 조건 ‘(3)’에 따라 집합 Q를 탐색합니다. 이때 Q에는 V의 도시명들이 대입되어 있음으로 정상적으로 다음 절차를 수행하게됩니다.

조건 ‘(4)’에 따라 시작 지점 a에서부터 가장 소요시간이 짧은 도시는 자기자신인 스페인임으로 스페인을 선택하고, 집합 Q 에서 도시명을 제거합니다. 그리고 스페인과 항공편으로 연결된 도시인 영국, 벨라루스, 그리스를 u로 지정하고 a에서부터 u까지의 소요시간을 구합니다.

계산된 소요시간은 아래와 같으며 ‘a ~ u 까지의 소요시간’에 대한 표기를 ‘d[ u ]’로 표기하겠습니다.
(아래의 계산 결과는 생략된 ‘d[스페인] ⇒ 0h’를 포함 하고 있습니다.)

d[영국] ⇒ 0h + 1h = 1h

d[벨라루스] ⇒ 0h + 6h = 6h

d[그리스] ⇒ 0h + 4h = 4h

 

 

집합 Q를 다시 탐색하고 공집합이 아님으로 a에서부터 가장 소요시간이 짧은 영국을 선택함으로 영국은 Q에서 제거됩니다.
(Q = { 영국, 스웨덴, 벨라루스, 그리스, 카자흐스탄} )

그리고 조건 ‘(5)’로 인하여 영국과 연결된 도시들인 스웨덴, 벨라루스가 u로 지정되고, a에서 u까지의 소요시간을 계산합니다. 계산된 소요시간은 아래와 같습니다.

d[스웨덴] ⇒ 0h + 1h + 2h = 3h

d[벨라루스] ⇒ 0h + 1h + 4h = 5h

 

 

집합 Q를 다시 탐색하고 공집합이 아님으로 a에서부터 가장 소요시간이 짧은 스웨덴을 선택함으로 스웨덴은 Q에서 제거됩니다.
(Q = { 스웨덴, 벨라루스, 그리스, 카자흐스탄} )

이후 스웨덴과 연결된 도시들인 벨라루스,카자흐스탄이 u로 지정되고, a에서 u까지의 소요시간을 계산합니다. 계산된 소요시간은 아래와 같습니다.

d[벨라루스] ⇒ 0h + 1h + 2h + 1h = 4h

d[카즈흐스탄] ⇒ 0h + 1h + 2h + 5h = 8h

 

 

집합 Q를 다시 탐색하고 공집합이 아님으로 a에서부터 가장 소요시간이 짧은 도시를 선택해야 합니다. 이때 스페인을 통해 계산되어 있던 d[그리스]와 스웨덴을 통해 계산된 d[벨라루스]가 4h의 동일한 최소 소요시간을 가지고 있습니다.
개요에서 설명한 것과 같이 데이크스트라 알고리즘이 우선순위 큐가 아님으로 큐의 FIFO 원칙에 의거하여 d[그리스]를 가장 소요시간이 짧은 도시로 선택하게 되고, 그리스는 Q에서 제거됩니다. (Q = { 벨라루스, 그리스, 카자흐스탄} )

이후 그리스와 연결된 도시들인 벨라루스, 카자흐스탄이 u로 지정되고, a에서 u까지의 소요시간을 계산합니다. 계산된 소요시간은 아래와 같습니다.

d[벨라루스] ⇒ 0h + 4h + 3h = 7h

d[카즈흐스탄] ⇒ 0h + 4h + 5h = 9h

 

 

집합 Q를 다시 탐색하고 공집합이 아님으로 a에서부터 가장 소요시간이 짧은 도시를 선택해야 합니다. 이때 위 계산 결과와 관계 없이 스웨덴을 통해 계산되었던 d[벨라루스]가 존재하며 a에서부터 가장 짧은 소요시간을 가진 경로로 벨라루스가 선택되어, 벨라루스는 Q에서 제거됩니다. (Q = { 벨라루스, 카자흐스탄} )

이후 벨라루스와 연결된 도시인 카자흐스탄이 u로 지정되고, a에서 u까지의 소요시간을 계산합니다. 계산된 소요시간은 아래와 같습니다.

d[카즈흐스탄] ⇒ 0h + 1h + 2h + 1h + 3h = 7h

 

 

다시 집합 Q를 탐색하고 공집합이 아님으로 a에서부터 가장 소요시간이 짧은 카자흐스탄을 선택함으로 Q에서 제거됩니다.
(Q = { 카자흐스탄 } )

 

최종적으로 Q에 남아 있는 도시명이 없음으로 최소 소요시간의 계산이 종료됩니다.

 

 

 

---

 

 

 

3. 정리

위와 같은 절차를 통해 항공편을 통해 스페인에서부터 카자흐스탄까지 걸리는 최소 소요시간은 7시간이며,
환승 경로는 스페인 → 영국 → 스웨덴 → 벨라루스 → 카자흐스탄이 된다는것을 알 수 있었습니다.

 

 

 

 

참고자료

한국방송통신대학교 - 이산수학(손진곤 교수님 강의 자료)

큐와 우선순위 큐 - https://chanhuiseok.github.io/posts/ds-4/

유럽 지도(백지표 - 내용 직접 가공) - https://greenblog.co.kr/2021/07/05/유럽-지도-3가지-종류-무료-다운로드/

위키백과
- https://ko.wikipedia.org/wiki/데이크스트라_알고리즘
- https://ko.wikipedia.org/wiki/에츠허르_데이크스트라