코드 14-3은 데이크스트라 알고리즘을 구현한 코드입니다. 최단 경로가 드러난 정점 집합 S가 있고 시장 정점의 distance는 0입니다. 최소 힙에는 (distance, v)를 넣습니다. S가 그래프의 모든 정점 집합이 될 때까지 최소 힙에서 정점을 하나씩 꺼내 옵니다. 꺼내 온 정점은 S에 포함시킨 후 인접 정점을 구하고 relaxation 연산을 합니다. S에 그래프의 모든 정점이 포함되었다면 while 문을 빠져나와 s, distance, p를 ShortestPath 객체로 반환합니다. 앞서 살펴본 그림들과 비교하며 데이크스트라 알고리즘의 실행을 직접 확인해 보기 바랍니다.
테스트 코드를 작성하고 잘 동작하는지 확인해 봅시다.
코드 14-4
if __name__ == "__main__":
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 3)
g.add_edge(1, 3, 5)
g.add_edge(2, 1, 5)
g.add_edge(2, 3, 8)
g.add_edge(3, 1, 4)
g.add_edge(3, 2, 12)
source = 0
sp = g.dijkstra(source)
for i in range(g.vertex_num):
print(f"distance[{i}] : {sp.distance[i]}, p[{i}] : {sp.p[i]}")
dest = 3
print(f"path from {source} to {dest}")
sp.print_shortest_path(dest)
print()