13장에서 프림 알고리즘을 구현할 때 최소 힙을 만들면서 decrease_weight 연산을 구현했습니다. 그런데 대부분의 언어가 제공하는 힙을 유심히 살펴보면 decrease_weight 연산을 제공하는 힙은 없습니다. 그렇다면 이 상황에서는 항상 decrease_weight를 위해 힙을 다시 구현해야 할까요? 그렇지 않습니다. 한 가지 방법이 있습니다. 힙 외부에 distance라는 배열을 따로 두고 relaxation을 할 때 새로운 거리를 키로 하는 요소를 힙에 push합니다. distance 배열도 달라진 거리를 변경합니다. 그리고 이후 힙에서 pop을 했을 때 distance 배열 값과 비교합니다. 힙에서 pop한 어떤 정점에 대한 거리가 distance에서 어떤 정점에 대해 저장해 놓은 거리와 다를 경우 이 요소는 relaxation 이전에 push한 요소이므로 버립니다. 이렇게 구현하면 decrease_weight() 메서드를 구현하지 않아도 됩니다.

이 내용을 코드로 구현해 보겠습니다. 먼저 파이썬이 제공하는 heapq 모듈을 이용해서 MinPriorityQueue 클래스를 구현하고, 출발점과 함께 경로 정보를 가지고 있는 ShortestPath 클래스를 정의하겠습니다.¹