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

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

한 꼭짓점을 "소스" 꼭지점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘

 

bfs에서는 최단 경로를 구하는 것이지만 다익스트라 알고리즘은 최단 시간(거리) 경로를 찾는 알고리즘이다

 

위 그림에서 A에서 B까지 가는 최단 경로를 찾을려면

1. 먼저 각각의 경로로가는 거리를 초기화한다

A = 0

B = null

C = null

D = null

E = null

 

2. A에서 갈 수 있는 경로 B, C 거리는 넣는다

A = 0

B = 5

C = 2

D = null

E = null

 

3. B에서 갈 수 있는 경로 D 거리를 넣는다

A = 0

B = 5

C = 2

D = 7

E = null

 

4. C에서 갈 수 있는 경로 B, E 거리를 넣는다

B로 가는 경로가 2 + 2 = 4 이므로 기존 A에서 B로 가는 거리 5보다 작으므로 수정해준다

마찬가지로 D까지 가는 경로도 수정해준다

A = 0

B = 4

C = 2

D = 6

E = 9

 

5. D에서 갈 수 있는 경로 E 거리를 넣는다

E로 가는 거리가 2 + 2 + 2 + 1 = 7 이므로 기존 E로 가는 경로 9보다 작으므로 수정해준다

A = 0

B = 4

C = 2

D = 6

E = 7

 

따라서 A에서 E로가는 최단 경로(거리)는 7이다.

 

참고

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98