4킬로미터 더 가는데, 20분 먼저 도착한다.
지도에 두 번째 숫자를 적기 전에는 내비게이션이 틀린 것처럼 보인다. 거리는 얼마나 많은 길을 지나야 하는지를 나타낸다. 시간은 그 길을 얼마나 빨리 지날 수 있는지에도 달려 있다. 일부러 만든 이 작은 도로망에서는 거리 대신 시간을 물었을 뿐인데 답이 완전히 달라진다.
무엇을 비용으로 셀지 정해야 가장 좋은 길도 정할 수 있다.
둘 다 맞는 두 가지 답
S에서 출발해 T에 도착한다고 하자. 위쪽 길은 A와 B를 거치며, 2킬로미터짜리 구간 세 개를 합쳐 총 6킬로미터다. 모든 구간의 속도를 시속 12킬로미터로 가정했으므로 구간마다 10분이 걸린다. 아래쪽 길은 C와 D를 지나 총 10킬로미터지만, 전 구간을 시속 60킬로미터로 이동한다고 가정한다. 전체 소요 시간은 10분이다.
따라서 거리가 가장 짧은 길은 30분, 시간이 가장 짧은 길은 10분이 걸린다. 두 답은 모순되지 않는다. 서로 다른 질문을 풀었기 때문이다. 위아래 길을 잇는 작은 연결 도로들도 있다. 덕분에 이 그림은 따로 떨어진 두 선이 아니라 하나의 네트워크가 된다. 잠시 뒤 가정을 바꾸면 이 연결들이 중요해진다.
지도를 비용 목록으로 바꾸기
그래프 알고리즘에서 교차점은 노드이고, 이동 가능한 연결은 간선이다. 각 간선에는 그 연결을 사용하는 비용인 가중치가 붙는다. 첫 번째 계산에서는 킬로미터가 가중치다. 두 번째에서는 거리를 속도로 나눈 뒤 60을 곱한 분 단위 시간이 가중치다. 그림 속 선의 모양은 계산에 들어가지 않는다.
이 점을 놓치기 쉽다. 반듯하게 그려진 선이 짧은 이동을 보장하지는 않는다. 이 그림은 축척에 맞춰 그리지 않았고, 거리는 따로 정했다. 실제 경로 탐색에도 지점 사이의 직선거리만이 아니라 도로 연결과 통행 제한이 필요하다. 가까이 보이는 다리라도 현재 있는 강변에서는 진입할 수 없을 수 있다.
Dijkstra는 현재 비용이 가장 작은 곳부터 살핀다
Dijkstra 알고리즘은 S의 비용을 0으로 두고 다른 노드의 비용은 아직 모르는 상태에서 시작한다. 비용이 확정되지 않은 노드 중 현재까지의 합계가 가장 작은 노드를 골라 연결된 길들을 확인한다. 더 싼 경로를 찾으면 이웃 노드의 비용을 갱신한다. 어떤 이전 노드에서 그 개선이 나왔는지도 기억해 마지막에 경로를 복원한다.
간선의 가중치가 음수가 아니어야 이 방식이 성립한다. 앞으로 더 이동해도 이미 지불한 비용을 되돌릴 수 없기 때문이다. 목적지의 비용이 확정되면 주어진 가정 아래에서 최소가 된다. 알고리즘 자체는 지각이나 경치, 편리함을 이해하지 못한다. 그런 우선순위는 탐색 전에 모델과 가중치로 표현해야 한다.
18분이 더해지면 달라지는 선택
이제 C–D 구간에 지연을 더하고 다시 계산해 보자. 원래 가장 빠르던 경로는 10분에 지연 시간을 더한 만큼 걸린다. 지연이 18분이면 다른 경로와 28분으로 동률이 된다. 지연이 더 커지면 연결 도로를 이용해 C–D를 피하는 경로가 최적이 될 수 있다. S–C–A–B–D–T로 이동하며 거리는 13킬로미터다.
한 번 선택된 경로가 계속 최적일 수 없는 이유다. 지연이 20분일 때 원래의 빠른 경로를 그대로 따르면 30분이 걸리지만, 다시 탐색하면 28분짜리 길을 찾는다. 물론 새 결과도 갱신한 가정만큼만 믿을 수 있다. 여기서 지연은 양방향에 동일하게 더한 고정 시간이지, 이동 중 계속 바뀌는 교통 예측이 아니다.
숫자 하나에 숨어 있는 우선순위
환승을 줄이고 싶은 사람도, 통행료를 피하고 싶은 사람도 있다. 계단 없는 경로가 필요하거나 느리더라도 더 안전하게 느껴지는 길을 택할 수도 있다. 어떤 조건은 탐색 전에 사용할 수 없는 간선을 없애는 방식으로 처리해야 한다. 다른 조건은 비용에 넣거나 별도 선택지로 보여 줄 수 있다. 모든 것을 점수 하나로 합칠 수도 있지만 환산 자체가 결정이다. 통행료 한 번을 아끼기 위해 몇 분을 더 쓸 것인가?
‘가장 빠르다’는 말조차 정의가 필요하다. 예상 소요 시간이 가장 짧은 길과 정해진 시각에 도착할 가능성이 가장 높은 길은 다를 수 있다. 이 고정 속도 예제에는 불확실성이 없으므로 그 문제를 풀 수 없다. 한 가지 차이를 분명히 설명할 뿐, 길 찾기의 모든 일이 몇 번의 덧셈으로 끝난다고 주장하지 않는다.
답을 믿기 전에 목표를 읽기
두 경로 추천이 다르면 각각 무엇을 최소화하며 어떤 제한을 알고 있는지 비교해 보자. 출발 시각, 이동 수단, 도로 폐쇄 여부와 함께 도보나 대기 시간이 포함되는지도 확인할 만하다. 이런 정보는 화면의 선이 얼마나 곧아 보이는지보다 중요할 수 있다.
이 습관은 지도 밖에서도 쓸모가 있다. 배송 계획, 네트워크 연결, 생산 단계도 선택 사이를 지나는 경로로 표현할 수 있다. 탐색은 정확해도 목표가 불완전할 수 있다. 알고리즘을 개선하기 전에, 계산 중인 비용이 정말 중요한 것을 측정하는지 묻는 편이 더 도움이 될 때가 많다.
더 읽어 보기
NetworkX: Dijkstra path and edge weights ↗SciPy: Dijkstra shortest paths and limitations ↗공식 문서와 함께 읽으면 좋은 자료입니다.