Dijkstra Algorithm Explained
개요 이 글은 자동차 내비게이션의 경로탐색 또는 그래프 이론에서 접하는 최단거리 탐색에 대해 설명한다. 출발지와 목적지 사이의 최단거리 경로탐색에 활용되는 알고리즘으로는 다익스트라 알고리즘이 대표적이라 할 수 있다. 다익스트라 알고리즘이 내부적으로 어떤 처리과정을 거쳐 결과를 만들어내는지에 대해 살펴보도록 한다. 다익스트라를 이용한 최단거리 찾기 그래프 이론에서 그래프는 링크(edge)와 노드(vertex)로 구성된다. 링크에 가중치(weight)가 적용되는 그래프를 가중치 그래프(weighted graph)라고 하며 이 가중치 그래프 상에서 출발지 노드가 주어졌을 때 다익스트라 알고리즘은 이 출발지 노드와 연결 가능한 모든 목적지 노드들 사이의 최단거리 경로와 거리(가중치의 합)를 구해낸다….