[알고리즘] 최단 경로찾기 ? 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다.

다익스트라의 최단 경로 탐색 알고리즘은 사이클이 없는 방향성 그래프에 한해서만 사용 가능.

 

동작 방식

1. 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화한다.

 

2. 시작 정점의 경로 길이를 0으로 초기화 하고(시작에서 시작까지는 0이므로), 최단 경로에 추가한다.

 

3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가.

만약 추가하려는 인접 정점이 이미 최단 경로 안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우, 다른 선행 정점을 지나던 기존의 경로를 현해 정점을 경유 하도록 수정.

 

4. 그래프 내의 모든 정점이 최단 경로에 소속될때까지 3번 과정 반복

 

 

예제

B에서부터 시작한다. B의 가중치 비용은 0이다. 주변에 있는 정점 A/C/F 간선의 비용을 해당 정점들에 저장해준다.

 

 

 

 

그리고 각각으 정점들에 있는 주변의 정점에 본인이 가지고 있던 비용을 추가로 더 해준다.

 B-A까지 35였으므로 A에서 E까지 이르는 비용 247을 더한 282를 E정점에 저장해주고,

B-C으로 있던 가중치 값에 B-C-D를 모두 더 하여 243, B-C-G는 220으로 저장해준다.

 

 

 

다음으로 정점 F에 인접한 정점들을 살펴보면 기존 B-A-E로 저장 되있던 282보다 B-F-E의 값은 150+82로 232이다.

기존 값보다 낮은 가중치 값으로 연결이 가능함으로 기존 경로 B-A-E는 폐기하고, 새 경로 길이를 232를 E에 저장해준다.

마찬가지로 B-C-G의 값 346보다 B-F-G의 가중치 값이 304로 더 낮으므로 기존 경로는 폐기하고 새로운 경로를 G에 저장해준다.

나머지 경로를 마찬가지로 계산해주고

최단 경로 탐색이 끝이 났다. B에서부터 해당 정점에 이르는 경로상에 있는 모든 간선들의 가중치를 합한것이다.

 

 

 

 

참고용

blog.naver.com/ndb796/221234424646

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