길의 비용을 정하는 일
골목길은 짧아도 신호등과 회전이 많습니다. 큰길은 멀지만 일정한 속도로 이동할 수 있습니다. 같은 출발점과 도착점이라도 목표가 거리 최소인지 시간 최소인지에 따라 비교할 숫자가 달라집니다.
경로를 선의 길이로만 보면 1.5km가 유리합니다. 도착까지 걸리는 분을 계산하면 6분이 유리합니다. ‘가장 짧다’라는 표현을 사용할 때 어떤 단위와 기준을 선택했는지 표시해야 합니다.
교차로를 연결한 그래프
도로를 점(교차로)과 선(도로 구간)으로 그려 봅시다. 선마다 거리 또는 이동 시간을 ‘가중치’로 붙입니다. 경로의 비용은 지나간 선의 가중치를 더해 계산합니다.
직접 도로가 4분이라도 우회 경로가 1분과 2분으로 이어지면 합계 3분이 더 빠릅니다. 중간 교차로의 개수로만 답을 고를 수 없습니다. 그래프에서는 경로가 지나간 모든 간선의 비용을 합산해야 합니다.
조건이 바뀌면 다시 계산
큰길이 공사로 막혀 이동 시간이 12분으로 늘어난 상황을 설정합니다. 골목길 10분이 더 빠른 길로 바뀝니다. 도로의 이름이나 출발점은 그대로인데 선택을 바꾼 원인은 가중치의 변경입니다.
이 예시는 음수가 없는 이동 시간을 사용하므로 다익스트라 알고리즘의 기본 조건에 맞습니다. 다익스트라 알고리즘은 지금까지 확인한 출발점으로부터의 최소 누적비용을 이용해 경로를 탐색합니다.
계산과 실제 길안내
실제 내비게이션은 예상 정체, 회전 제한, 통행 조건처럼 다양한 정보를 반영합니다. ‘최단 시간’이라는 답은 입력한 시간 추정치와 도로 연결이 정확하다는 조건 아래에서 성립합니다.
길 안내를 읽을 때 예상 6분이라는 표시와 반드시 6분에 도착한다는 보장을 구별합니다. 언제, 어떤 교통 조건에서 측정했는지 묻는 일이 숫자 하나보다 중요한 경우가 많습니다.