알고리즘> 그래프> 다익스트라 알고리즘 탐색 기법

 

음과 같은 그래프가 있을 경우 파이썬으로 표현한 것

저번에 코드블럭에다가 소스코드를 써봤는데 가독성이 넘 안좋은 것 같아서  이번에는 캡처를 이용함

 

생각보다 단순하다.. 설명을 붙이자면 

 

distances 는 시작점에서 각 노드까지 최소 거리를 저장한 배열.

처음에는 시작점을 제외하고 나머지는 무한으로 설정한다.

queue 는 시작점에서 어떤 노드까지 길이를 담아놓은 배열인데, 다뤄야 할 목록이라고 생각하면 됨.

작업할 게 없을 때까지 반복한다.

현재 노드와 길이를 뽑는다.

만약 최단 거리가 있는데 그것보다 길이가 긴 경로를 가진 노드를 꺼냈을 경우 다음 노드로 스킵

내가 뽑은 노드의 주변을 탐색한다.

주변 노드까지 길이를 distance로 저장

만약 이 distance가 기존에 있던 최단거리릴 갱신했을 경우 덮어씌운다.

 그리고 덮어씌운 노드를 queue에 저장한다. 이렇게 해서 경로 길이를 누적시킬 수 있다.

 

 

이렇게 하면 시작점에서 각 노드까지 최소거리를 구할 수 있다.