최단경로 알고리즘(2)/ 힙을 사용한 다익스트라 알고리즘

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 힙이란?

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 최소 힙은 가장 작은 우선순위부터 꺼내는 방식이고 최대 힙은 값이 높은 데이터부터 꺼내는 방식이다. 리스트를 사용하는 경우 삽입시간은 O(1), 삭제는 O(N)시간이 걸리는 반면 힙을 사용하는 경우 삽입하고 삭제하는데 O(logN)만큼의 시간을 보장한다. 

 

▷구현 

>최소힙 구현

> 최대힙 구현

 

 

▶ 힙을 활용한 다익스트라 알고리즘

힙을 사용하여 개선된 다익스트라 알고리즘을 구현할 수 있다. 알고리즘이 동작하는 원리는 이전 포스팅에서 기록한 원리와 동일하지만 현재 가장 가까운 노드를 저장하기 위해 힙자료구조를 사용한다는 점에서 수행시간을 더 줄일 수 있다. 

> 시간복잡도: 노드의 개수를 V로, 간선의 개수를 E로 잡았을 때 반복문이 노드 개수 V이상의 횟수로는 처리되지 않기 때문에 보통  O(ElogV)의 시간복잡도를 가진다. 

 

▷ 예시

힙은 [[(거리, 노드), (거리, 노드)...]]로 표현하였고 노드번호에 따른 최단거리는 [노드1에 대한 거리, 노드2에 대한 거리...]로 표현하였다.

> 1에서 출발. 거리는 0. -> [[(0,1)]] / [0,INF,INF,INF,INF]

> 노드 1에서 갈 수 있는 노드 탐색, 1에서 2,4,5로 이동 가능. -> [[(2,2),(2,4),(5,5)]] / [0,2,INF,2,5]

> 힙에서 노드 2를 꺼내 2에서 갈 수 있는 노드 탐색. 2에서 3으로 이동가능 -> [[(2,4),(3,3), (5,5)]] / [0,2,5,2,5]

> 힙에서 노드 4를 꺼내 3으로 가는 거리는 2+4=6으로 기존 5보다 크므로 패스. 4를 거쳐 5로 가는 거리 역시 6으로 기존 5보다 크므로 패스. 힙과 리스트 둘다 변화 없음 -> [[(3,3), (5,5)]] / [0,2,5,2,5]

> 힙에서 노드 3을 꺼내 4로 가는 거리는 5+4=9, 5로가는 거리는 5+2=7로 현재 최단거리보다 크다. 이는 4와 5가 이미 이전에 방문된 노드임을 뜻하기도 한다. 

> 힙에서 노드 5를 꺼냈지만 갈 수 있는 노드가 없기에 힙과 리스트에 아무 영향을 주지못하고 종료된다. 

 

위의 구현 방식은 최단 거리가 짧은 노드를 선택해 탐색하는 과정을 힙을 통해 구현하기 때문에 빠른 실행이 가능하다. 

 

▷ 구현

데이터를 입력받는다.

 

알고리즘을 구현한다. 이전 포스팅에서의 코드에선 현재 방문한 노드와 인접한 노드의 거리 중 최단거리를 탐색하는 함수를 따로 선언해야했지만, 여기서는 최소값을 찾을 수 있는 힙을 사용하여 해당 함수를 간단히 구현할 수 있다. 

힙에선 요소가 다 빠져서 빈 리스트가 되어있는 것을 볼 수 있고 1에서 출발하는 모든 노드와의 최단거리가 distance의 1에서 5까지의 인덱스에 기록되있는 것을 볼 수 있다.