가중치 그래프에서는 Dijkstra 알고리즘으로 최단 경로를 찾을 수 있다.

Dijkstra 알고리즘을 사용하기 위해서는 그래프 Node 에 3가지 변수를 저장해야 한다.

1 번째는 distance

2 번째는 predecessor

3 번째는 complete

이번 장에서는 이 변수들이 각각 어떤 역할을 하는지 알아보겠다.

distance 설명

distance 변수는 시작점에서 이 Node 까지의 거리이다.

시작점에서 이 Node로 오는 경로는 여러 개이다.

그럼 어떤 값을 저장해야 할까?

이 distance 는 최단 거리 예상치라고 생각하면 된다.

이게 무슨 말이냐면, Node를 한꺼번에 다 방문하는 게 아니라 하나씩 방문한다.

이 distance 는 현재까지 알고 있는 정보들만 갖고서 계산한 최단 거리인 것이다.

헷갈릴 수 있는 개념이다.

예시를 보자.

아래 그래프에서 A - B - D 경로는 찾았지만 A - C - D 경로는 아직 못 찾았다고 가정하자.

그러면 현재까지 아는 선에서 A 에서 D 까지의 최단 경로는 A - B - D 이다.

A - C - D 가 더 짧더라도 그 경로는 아직 못 봤으니깐!

그러면 시작점부터 D 까지 최단 거리 예상치는 A - B - D 길이 4 + 2를 해서 6이다.

Node D 의 distance 변수로 6을 저장하면 된다.

만약 Node D 로 오는 더 짧은 경로를 찾으면 그 때, distance 를 수정해 주면 된다.

predecessor 설명

이 predecessor 변수는 뭘 하는 것이냐면 현재까지 찾은 최단 경로에서 바로 직전의 Node 이다.

방금 전 그래프로 똑같은 예시를 들어보겠다.

아래 그래프에서 A - B - D 경로를 찾았지만, A - C - D 경로는 아직 못 찾았다고 가정하자.

그럼 현재 아는 정보로는 A 에서 D 까지의 최단 경로는 A - B - D 이다.

그러면 D 의 predecessor 는 이 경로에 있는 D 의 직전 Node B 이다.

사실 A - C - D 가 더 짧은 경우지만 그 경로는 아직 찾지 못했기 때문에 반영이 안 된 것이다.

D 로 오는 더 짧은 경로를 찾으면 그때 D 의 predecessor를 수정해 주면 된다.

distance 랑 로직이 비슷하다.

complete 설명

complete 변수는 어떤 Node 를 완전히 파악했는지 표시해두는 목적으로 사용한다.

처음에는 모두 False 이다.

어떤 Node 를 발견했다고 해서, 그 Node 로 가는 최단 경로를 찾았다고 할 수는 없다.

그런데 Node 들을 하나씩 방문하다 보면 확신이 생기기 시작한다.

어떤 Node 에 대한 확실한 최단 경로를 찾았다면 그때 그 Node 의 complete 변수를 True로 수정해 주면 된다.

이제 이 Node 를 완전히 파악했다고 표시해두는 것이다.