[알고리즘] 15. 최단 경로 탐색

공부한 날짜: 2021. 11. 04

 

-최단경로 탐색: 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최소값이 되게 만드는 경로를 찾는 알고리즘

 

-다익스트라 알고리즘 

: '경로의 길이'를 감안해서 간선을 연결한다는 점이 '간선의 길이'를 이용해 어떤 간선을 먼저 연결할지 결정하는 프림 알고리즘과 다름 

 

-동작 순서(아직까지는 ㄷ.이 무슨말인지 모르겠음,,)

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

ㄴ. 시작 정점의 경로 길이를 0으로 초기화 하고 최단 경로에 추가

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

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

ㄹ. 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 ㄷ. 과정을 반복한다 

 

-다익스트라 구현