다익스트라 알고리즘(Dijkstra algorithm)

다익스트라 알고리즘이란?

어느 한 정점에서 다른 정점까지의 최단 경로를 찾는 문제를 최단 경로(Shortest Path) 문제 라고 하는데 그 중 대표적인 알고리즘이 다익스트라(Dijkstra) 알고리즘이고 탐욕(Greedy)알고리즘의

알고리즘 설명

• S = 방문한 노드들의 집합
• d[v] = 출발정점 A에서부터 최단거리가 확정되지 않은 각 점 v까지의 최단 거리
• Q = 방문하지 않은 정점들의 집합
  

1. 아직 방문하지 않은 정점들과의 거리는 전부 무한(∞)으로 갱신한다. (단,d[A]=0)
2. 출발정점과 이웃한 정점들을 d[v]에 기록한다.
3. 기록된 정점들 중 최소값을 선택하여 Q에서 제거하고 방문한 정점의 집합 S에 넣는다.
4. S에 들어간 정점과 이웃한 정점들을 모두 탐색하여 d[v]에 기록한다.
5. 위의 3번과 4번 과정을 반복한다.
   이 때 기존의 d[v]보다 더 빠른 경로가 발견되면 해당 정점의 최단거리를 갱신한다.
6. Q가 공집합이 되면 모든 정점의 최단거리를 확정한다.

다익스트라 알고리즘은 구글 웹사이트의 지도 서비스, 자동차 내비게이션, 네트워크 통신분야, 교통공학 등 다양한 분야에서 유용하게 활용된다고 한다.