다익스트라(Dijkstra) 알고리즘(이상희 부장님)

[자료구조 목차]

1. 다익스트라 알고리즘 개요

 

1) 다익스트라 알고리즘 정의

• 너비우선탐색(BFS) 기반으로 하나의 시작 정점에서 부터 다른 모든 정점들까지 증가하는 거리의 순으로 최단 경로를 찾는 탐색 알고리즘
• 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘

 

2) 다익스트라 알고리즘의 특징

• 방향/무방향그래프 관계없이 사용가능
• 가중치가 음수인 edge 가 존재할 경우 사용이 불가함

 

3) 다익스트라 알고리즘 활용

• 네비게이션의 도시간 최단 거리 탐색
• 미로탐색 알고리즘
• 리우팅(OSPF) 프로토콜
• 공업입지론에서 최소 운송비 지점 구하기
• 루빅스 규브 해법
• A* 알고리즘 : 다이스트라 알고리즘 확장

 

2. 다익스트라 알고리즘 절차

1) 그래프 탐색과정 

 

 

 

2) 그래프 수행 절차

초기화 : 시작노드를 제외한 모든 노드의 거리정보를 무한대로 설정

시작노드를 기준으로 BFS 탐색으로 이웃 노드의 거리정보를 Update하여 최단거리 노드 탐색 및 방문을 반복적으로 수행

절차	기준 노드	이웃노드(거리정보)	거리정보 update(작을 경우)	탐색(gray)	방문완료(black)
a	s	t=∞ y=∞		s
b	s	t=∞ y=∞	t=10 (update) y=5 (update)	y	s
c	y	t=10 x=∞ z=∞	t=8 (s-y-t) (update) x=14 (s-y-x) (update) z=7(s-y-z) (update)	z	y
d	z	x=14	x=13 (x-y-z-x) (update)	t	z
e	t	x=13	x=9 (s-y-t-x) (update)	x	t
f	x				x

 

3. 계산 복잡성 및 단점

1) 계산 복잡성

• BFS 적용 미방문노트 탐색 O(V), 한노드당 엣지의 기대값 E / V
• 평균 복잡성 O(V2)  [ O(V2+E) ]

2) 단점 및 해결방법

• 가중치가 음수인 경우 탐색 불가
• 해결방법 양수화(모든 거리에 |음수거리|+한후 적용이 끝나면 절대값 - )

 

참조: 다익스트라 알고리즘 · ratsgo's blog