코드 14-1에서 ShortestPath 클래스에 정의된 print_shortest_path를 유심히 살펴보기 바랍니다. 매개변수로 목적 정점 dest를 전달하면 시작 정점부터 경로를 출력해 주는 메서드입니다. 재귀적으로 구현된 것을 알 수 있습니다. 경로가 a->…f->g라면 a->f까지 경로를 출력한 후 g를 출력하면 될 것입니다. 재귀 함수로 구현하기 좋은 구조이지요.

코드 14-2

class Graph:
    # 모든 가중치보다 충분히 큰 수
    BIG_NUMBER = 2000
    def __init__(self, vertex_num):
        self.adj_matrix = [[None for _ in range(vertex_num)] for _ in
                            range(vertex_num)]
        self.vertex_num = vertex_num

    def add_edge(self, u, v, w):
        self.adj_matrix[u][v] = w

코드 14-2를 보면 데이크스트라 예제에서는 그래프 표현을 인접 행렬로 한 것을 알 수 있습니다. 또 distance 배열을 초기화할 때 math 모듈의 inf를 쓰지 않고 에지가 가질 가중치의 모든 합보다 충분히 큰 값 BIG_NUMBER를 사용합니다. relaxation을 하던 도중 정수 오버플로가 날 수 있기 때문인데요. 파이썬은 int 형 범위를 벗어나면 자동으로 long long으로 변경해 주므로 정수 오버플로가 생길 확률은 매우 적습니다. 이제 데이크스트라 알고리즘을 구현해 봅시다.