알고리즘 - 다익스트라(dijkstar) 알고리즘

최단 경로를 찾기 위해 사용하는 알고리즘.

 

하나의 출발점부터 모든 정점으로의 최단 거리를 계산하는 알고리즘.

 

1. 시작점 결정

2. 전체 거리를 무한대(코드상에서는 0)로 설정.

3. 현재 위치에서 갈수 있는 정점 저장. 전체거리를 최소로 늘릴수 있는 경로를 갱신. 불가능하면 스킵.

4. 선택하지 않았던 정점중 가장 짧은 거리에 있는 정점을 현재 정점으로 갱신.

5. 3~4 번 반복. 

 

단순 구현으로는 

시작점에서 각 정점에 대한 거리를 배열에 저장해가면서 각 정점으로의 최단 경로들을 찾아가는 방법이 있다...

10개의 정점을 가지는 그래프라고 가정할때 10개의 요소를 가지는 배열에 순서대로 각 정점에 대한 최단 경로를 저장하는 것. 당연히 자기 자신으로의 경로는 0의 거리를 가진다.

 

효율적인 구현으로는 

우선순위 큐를 이용해 구현하는 방식.

항상 시작점 기준 거리가 짧은 순서대로 정렬되어 정점이 저장되므로,

큐의 앞에서부터 데이터를 꺼낸다면 항상 최단거리를 반환하게 된다.