[최단 경로 트리] 다익스트라 알고리즘[Dijkstra]

다익스트라 알고리즘을 설명하기 전에, 최단 신장 트리에 대해 설명해보자.

 

신장 트리란 그래프 내의 모든 정점이 연결되어 있으면서 사이클이 존재하지 않는 트리이다.

따라서 신장 트리는 N개의 정점을 정확히 N-1개의 간선으로 연결하게 된다.

 

 

다익스트라 알고리즘은 출발 지점을 정하여, 다른 모든 지점까지의 최단 경로를 찾는 것이다.

 

 

예를 들어보면,

 

최단 경로 찾기 예시

 

A를 출발 지점으로 두고 시작해보자.

 

A의 최단 거리값은 0으로, 나머지 최단 거리값은 무한으로 설정한다.

 

이제 A와 연결된 B, C의 거리 값을 조정하자.

여기서, 시작점 거리값 + 아크 값 < 도착점 거리값이라면, 도착점 거리값을 더한 값으로 낮춘다.

 

A 기준

 

 

방금 했던 것을 무한 반복할껀데, 이번에는 B를 기준으로 한다.

 

B 기준

 

C 기준

 

D 기준

 

E 기준

 

F 기준

 

 

 

최종적으로, 이런 결과가 나오게 된다.

 

최종 결과

 

거리가 짧을 때만 값을 낮췄기 때문에, 최단 거리를 구할 수 있었다.

 

 

 

 

 

이 게시글은 아래 링크를 참고했습니다.

https://www.zerocho.com/category/Algorithm/post/584bd46f580277001862f1af