개선된 다익스트라 알고리즘 . 2

V 는 노드의 개수를 의미한다
O(V) 번에 걸쳐서 최단 거리가 가장 짧은 노드를 찾기 위해 O(V) 번 선형 탐색을 해야 하므로
전체 시간 복잡도는 O(V^^2) 이다
더욱 효율적으로 동작하는 알고리즘을 설계할 필요가 있다.

 

 

 

 

 

최소 힙은 값이 낮은 데이터부터 꺼내는 방식으로 동작하고 (오름차순)
최대 힙은 값이 높은 데이터부터 꺼내는 방식으로 동작한다 (내림차순)

 

단순히 리스트로 우선순위 큐를 구현했을 때, 
데이터를 삽입할 때는 단순히 데이터를 맨 뒤에 차례대로 넣으면 되기 때문에 O(1)(상수 시간) 이 걸리지만
데이터를 삭제할 때는 전체 데이터를 순회하며 우선순위가 가장 높은 데이터가 무엇인지 확인해야 하기 때문에
O(N)(선형 시간) 이 걸린다

 

힙은 내부적으로 트리 구조를 이용하여 데이터의 삽입과 삭제를 O(logN)의 시간복잡도로 보장한다.

 

 

 

파이썬의 힙 라이브러리는 기본적으로 최소 힙(Min Heap) 방식으로 구현 되어 있기 때문에 우선순위가
낮은 원소부터 차례대로 꺼내지게 된다

 

어떤 데이터를 오름차순으로 정렬하고자 하면 
단순히 힙 자료구조에 모든 데이터를 넣었다가 다시 모든 데이터를 꺼내게 되면 
그렇게 꺼내진 데이터 순서 자체가 오름차순 정렬이 이루어진 형태이다

 

 

 

파이썬에서 최대 힙을 구현하고 싶으면
데이터를 힙에 넣기 전에 데이터의 부호를 바꿔서 넣은 뒤에
다시 데이터를 꺼낼 때 마찬가지로 부호를 바꿔서 꺼내주면 된다

 

 

 

 

 

 

 

 

 

최소 힙이기 때문에 거리가 작은 순서로 오름차순으로 정렬이 된다

 

 

 

노드는 같지만 거리가 더 짧은 경우가 갱신되면 밑에 사진처럼 정렬이 된다

 

 

(중간 생략)

 

갱신 여부가 다 False이기 때문에 우선순위 큐에 갱신하지 않는다 (코드에서는 continue 를 이용)

 

 

 

3번 노드는 이미 방문 처리가 된 노드이긴 때문에 무시한다

그리고 방문처리하는 배열을 따로 만들지 않고 최단거리 테이블과 비교해서 현재 노드 거리값보다
우선순위 큐에서 꺼낸 노드 거리값이 더 크면 현재 꺼낸 원소를 무시하게 만드는 방법이 사용될 수 있다. 

 

 

 

 

 

 

C++ 코드

C++ 에서는 우선순위 큐가 기본적으로 최대 힙으로 구현되어 있어서 데이터의 부호를 바꿔준다

 

 

 

자바 코드

자바 코드에서 최소힙을 구현하기 위해서 Comparable 인터페이스를 구현해서 하나의 클래스를 정의한 후
compareTo 메서드를 Override 했다  (무슨 소리인진 잘 모르겠다 ㅠ)

 

코드를 짤 때 최소힙으로 구현을 했기 때문에, 우선순위 큐에 원소를 그대로 넣는 방식으로 간단히 사용할 수 있다

자바에서는 큐에 데이터를 넣을 때는 offer() ,  데이터를 꺼낼 때는 poll() 메서드를 호출한다

 

 

 

큐에서 원소를 꺼내서 해당 노드를 처리할지 결정할 때 
현재 노드가 이미 처리된 적이 있으면 무시하기 때문에 
반복문(while문) 은 노드의 개수 V 이상의 횟수로는 처리되지 않는다

그렇기에 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 최대 간선의 개수이다.