데이크스트라 알고리즘

데이크스트라 알고리즘

이번 시간에는 데이크스트라 알고리즘의 동작 원리를 살펴보겠습니다.

데이크스트라 알고리즘(다익스트라 알고리즘, Dijkstra Algorithm) - ""

- 알고리즘 입니다.

위의 그래프에 데이크스트라 알고리즘을 적용할 것입니다.

우선 시작점인 S에 포커스를 둡니다

포커스에서부터 주위를 둘러봐서(BFS) '포커스된 노드 값 + 간선 값' 값을 '발견된 노드 값' 과 비교할 것입니다. 만약 포커스된 노드 값과 간선 값을 더한 값이 발견된 노드 값보다 더 작으면 더 작은 값(더한 값)으로 대체합니다. 위의 사진의 경우,

포커스된 노드 (S) : 0

간선 (S-e) : 4

발견된 노드 (e) : ∞

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하므로 대체합니다.

이므로 더 작은 값으로 대체합니다.

포커스된 노드 (S) : 0

간선 (S-d) : 3

발견된 노드 (d) : ∞

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하므로 대체합니다.

포커스된 노드 (S) : 0

간선 (S-b) : 3

발견된 노드 (b) : ∞

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하므로 대체합니다.

둘러보기를 끝낸 S를 무효화시키고 e로 포커스를 옮깁니다. S는 무효화 되었으므로 둘러보기에서 제외됩니다.

포커스된 노드 (e) : 4

간선 (e-c) : 8

발견된 노드 (c) : ∞

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하므로 대체합니다.

포커스된 노드 (e) : 4

간선 (e-d) : 8

발견된 노드 (d) : 3

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하지 않으므로 대체하지 않습니다.

S는 둘러보기에서 제외되었으므로 접근하지 않고 건너뜁니다.

둘러보기를 끝낸 e를 무효화시키고 d로 포커스를 옮깁니다.

포커스된 노드 (d) : 3

간선 (d-c) : 6

발견된 노드 (c) : 12

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하므로 대체합니다.

포커스된 노드 (d) : 3

간선 (d-b) : 1

발견된 노드 (b) : 7

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하므로 대체합니다.

둘러보기를 끝낸 d를 무효화시키고 b로 포커스를 옮깁니다.

포커스된 노드 (b) : 4

간선 (b-a) : 3

발견된 노드 (b) : ∞

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하므로 대체합니다.

둘러보기를 끝낸 b를 무효화시키고 c로 포커스를 옮깁니다.

포커스된 노드 (c) : 9

간선 (c-a) : 2

발견된 노드 (b) : 7

∴ '포커스된 노드 값 + 간선 값 < 발견된 노드 값' 이 성립하지 않으므로 대체하지 않습니다.

둘러보기를 끝낸 c를 무효화시키고 a로 포커스를 옮깁니다.

그러나 a 주변의 모든 노드가 다 무효화 되었으므로 수색을 진행하지 않습니다. 이렇게 모든 노드가 다 무효화 되었으므로 모든 작업을 종료합니다.

각 노드의 최소 비용은 위와 같습니다

선을 그으면 위와 같습니다

from http://sharpcoder.tistory.com/162 by ccl(A) rewrite - 2021-07-28 14:26:26