[최단경로] 최단경로 이동하기 ( 다익스트라 알고리즘 )

 

예제 ) 시작도시와 목표도시가 주어질 때, 목표도시까지 가는 최단 경로를 구하시오

 

 

시작도시 : A

목표도시 : E

 

 

 

 

다익스트라 알고리즘을 사용한다. 

 

각 노드마다 접근된 경로의 길이를 기록한다. 최단 경로이므로 최소길이만 기록한다. 

 

 

 

D노드와 C노드와 F노드는 다음과 같은 접근 경우를 가질 수 있다. 

 

 

 

 

경우 중 최소를 제외한 나머지는 제거한다. 이런 방식으로 각 노드의 최단 경로 길이를 구한다.

 

 

 

최소만 남긴다.

 

 

 

마지막으로 목표노드의 최단 경로 길이를 구해보자.

 

 

 

A에서 E까지 최단경로길이는 17km이다.

 

 

---

 

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성