다익스트라

그래프를 활용하여 최단 경로를 구할 수는 없을까? 최단경로 알고리즘은 크게 3가지가 존재한다. 이번 시간에는 다익스트라만 다루도록 하겠다. 다익스트라란? 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 정점 사이에는 가중치가 존재한다. 최단경로의 특징 정점 x까지 최단거리로 가기 위해서는 그 직전까지도 최단거리로 가야 한다. 위의 그림을 보면 1 - 6 - 2 - 3 - 8 - 7 순으로 이동한다. 최단경로의 특징을 이용하면 1~8까지 이동할 때에도 최단 경로로 이동한다. 그래서 최단경로 트리를 어떻게 만들 것인가? T(i) = i까지 도달하는 최단거리 -> 파란색 숫자 순서를 그림을 이용하여 천천히 설명하겠다. 보라 색원은 이미 탐색을 완료했다는 의미이다...

원문링크 : 다익스트라