Algorithm Dijkstra algorithm without direction

알고리듬 Dijkstra algorithm without direction을 알아보겠습니다.

​
Dijkstra(다익스트라, 데이크스트라) 알고리듬은 최단거리를 구할 때 사용합니다.
각 지점 간의 거리를 계속해서 업데이트합니다.
이번 시간에는 방향성이 없는 경우를 다룹니다.
​
개념은 간단합니다. 모든 경우에 대해서 경로 업데이트를 진행합니다.
이전에 지나갔던 길 보다 더 적은 값을 발견하면 다시 그 경로를 전체 탐색합니다.
더 이상 적은 값을 발견하지 못하면 프로그램은 종료되고 우리는 가장 최단 거리를 알게 됩니다.
​
​
다음과 같은 지도에서 3 -> 5로 가는 최단 경로를 구해봅시다.

각 지점 간의 관계는 다음과 같이 표시하기로 합니다.

[시작 지점, 시간, 도착 지점]

예를 들어 3 번 지점의 경우 [3, 2, 1], [3, 5, 4]로 표현될 수 있습니다.

​

지점은 총 5 개가 있고, 출발 지점은 3 번, 도착 지점은 5 번입니다.

맵은 다음과 같이 있습니다.

일단 모든 노드들의 관계를 저장할 리스트를 하나 만듭니다.

adjacent로 만들었고, 노드의 수에 맞게 2 중 배열로 만듭니다.

for 문으로 리스트에 해당하는 경로들을 넣어줍니다.

10 번째 줄에서 가는 경로를 넣고,

11 번째 줄에서 오는 경로를 넣습니다.

searching이라는 함수를 만듭니다.

1 번째 줄에서 heapq, heappush, heappop을 불러옵니다. queue의 PriorityQueue를 사용해도 되는데, Thread 신경 안 쓰고 속도적인 측면만 필요하다면 heapq를 사용합니다.

5 번째 줄에서 시작 점에서 이동할 때 걸리는 모든 시간을 저장할 take_time 리스트를 만들고 큰 수로 초기화 시킵니다.

8 번째 줄에서 시작점의 소요 시간을 0으로 만듭니다.

9 번째 줄에서 heap에 시간과 함께 시작 노드를 넣어줍니다.

11 번째 줄에서 탐색할 노드가 없을 때까지 반복을 합니다.

12 번째 줄에서 heap에 든 노드 중에 가장 소요되는 시간 값이 적은 값을 먼저 꺼냅니다.

14 번째 줄에서 현재 노드를 가져옵니다.

15 번째 줄에서 만약 현재 노드의 소요 시간이 저장되어 있는 값보다 크다면 continue를 합니다.

18 번째 줄에서 해당 노드의 인접 노드들을 모두 불러옵니다.

22 번째 줄처럼 다음 노드로 가는 저장된 시간과 저장된 현재 노드와 다음 노드의 시간을 더해서 비교합니다. 만약 이미 저장된 다음 노드 소요 시간이 더 크다면 갱신하고 heapq에 집어넣습니다.

26 번째 줄에서 모든 저장된 소요 시간에서 도착 노드의 값만 반환합니다.

41 번째 줄에서 위의 함수를 불러옵니다.

전체 코드입니다.

끝.

카테고리: Algorithm