최적 경로를 계산해 주는 다익스트라법
4-11 거리 뿐 아니라 다양한 조건에 따라 최적 경로를 찾아 준다.
위치를 파악하고 나면 지도상의 수많은 교차점들 중에 목적지로 가는 최적의 경로를 검색해야 한다. 예를 들어 그림의 0번에서 시작해서 4번으로 가려고 한다면 사람은 직관적으로 경우의 수를 시뮬레이션해서 1-3-6-5의 과정을 거치면 가장 최단 거리로 갈 수 있다는 것을 계산해 낼 수 있다. 실제 우리의 뇌가 진행하는 이런 계산 과정을 컴퓨터가 찾아낼 수 있도록 하는 로직으로 다익스트라법이 있다.
다익스트라이법 로직 예제 - 위키피디아 참조다익스트라법은 각 지점별로 출발점에 그 점까지 오는 최단거리를 순차적으로 하나씩 계산해 낸다. 제일 먼저 출발점 0에서 연결된 세 점에서 연결된 1/2/5번 노드까지의 거리를 비교해서 가장 짧은 노드 값을 확정한다(1번 노드-거리 7). 그리고 난 후에 앞서 확정한 0-1 조합을 새로운 출발 조합이라고 두고 거기에 연결된 새로운 연결들을 계산해 본다. 2번 노드의 경우 원래 거리가 9인데 1번을 거쳐 가는 거리는 10이므로, 그대로 9라는 값을 유지한다.
같은 방식으로 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문하고, 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신해서 그중 가장 짧은 거리를 업데이트를 계속한다. 이런 방식으로 진행하면, 각 노드별로 최단 거리가 계산되고, 목적지에 도달하기 위한 최적의 경로들을 쉽게 찾아낼 수 있다.
노드와 노드 사이의 링크의 물리량을 거리가 아니라 속도를 반영한 소요 시간이나 톨비, 탄소 배출량 등으로 설정하면 최단시간, 최적 연비 경로를 찾을 수 있다. 동일한 거리라도 고속도로에 가중치를 두거나, 막히는 구간에 불편한 정도를 팩터로 설정하면 고속도로 우선이나 편한 운전 경로로 안내도 가능하다. 그리고 중간 단계에 미리 계산해 두기 때문에 경로를 이탈해서 빠르게 재 탐색할 수 있는 장점이 있다.
