다익스트라(Dijkstra's) 알고리듬 간략 정리

 

그래프의 시작 정점에서 다른 정점까지의 최단 경로를 계산하는 알고리듬 중 하나입니다.

다익스트라는 매 상황에서 비용이 가장 적게 드는 경로를 선택해 최단 경로를 계산하며,

거리를 계산하던 도중 현재까지 알고 있던 경로 비용보다 새로 알게된 경로의 총 비용이 더 적다면 총 비용을 갱신합니다.

 

 

1) 시작 정점을 설정

2) 시작 정점을 기준으로, 인접한 정점까지의 최소 비용을 저장

3) 아직 방문하지 않은 정점 중, 총 비용이 낮은 정점을 선택

4) 해당 정점을 거쳐서 특정 정점으로 가는 경우를 고려하여, 그 특정 정점까지의 최소 비용을 갱신

5) 위 과정에서 3~4번을 반복

 

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

 

위 그래프의 경우, 1번에서 5번 정점까지 최단 경로의 비용을 계산하고 있고, 저장과 갱신을 반복해서 최종적으로 최단 경로를 계산하게 됩니다.

To	1	2	3	4	5	6
Cost(초기화)	0	∞	∞	∞	∞	∞
Cost(정점 1)	0	7	9	∞	∞	14
Cost(정점 2)	0	7	9	22 ( 7+15 < ∞)	∞	14
Cost(정점 3)	0	7	9	20 ( 9+11 < 22)	∞	11 ( 9+2 < 14)
Cost(정점 6)	0	7	9	20	20 (11+9 < ∞)	11
Cost(정점 4)	0	7	9	20	20 (20 < 20+6)	11

 

이 글은 아래 영상과 글을 보고 작성했습니다.

https://www.youtube.com/watch?v=tzUJ7GE1qVs

https://www.youtube.com/watch?v=611B-9zk2o4 

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm