[Do it!_Algorithm with Python] 5.2 Dijkstra

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python'

---

 

 

최단 거리를 구하는 알고리즘으로, 특정 노드에서 다른 노드까지 최단 거리는 몇인가?라는 문제에서 사용한다.

딴, edge의 가중치가 양수여야 한다.

기능	특징	시간 복잡도(node:V, edge:E)
출발 노드에서 모든 노드간의 최단 거리 탐색	Egde의 가중치는 모두 양수여야 한다.	O(E*logV)

 

▪️과정

 

1. 인접 리스트로 그래프 구현

인접 행렬도 가능하지만, 시간복잡도를 고려할 때 N의 크기가 커지는 것을 방지하기 위해 인접 리스트를 선택하자.

주어진 그래프를 인접 리스트로 표현

 

 

2. 최단 거리 배열 초기화

최단거리를 저장해주는 배열을 노드 개수만큼 만든다.

에서 출발하므로 노드1까지의 최단거리는 0, 그리고 나머지 노드들의 최단거리는 무한대(Max)로 초기화해준다.

최단거리 배열 만들고 거리 초기화해주기

 

 

3. 값이 가장 작은 노드 고르기

 

현재 최단거리 배열 값에서 가장 작은 노드를 고른다.

 

매번 업데이트 할때마다 최단거리 값이 가장 작은 노드를 고른다.

우선 출발할 때는, 출발 노드의 최단거리 값이 0으로서 가장 작으므로, 노드 1을 고른다.

 

 

 

 

4. 최단 거리 배열 update (방문 노드 체크하면서 이동하기!)

 

 

선택된 노드 1의 Array를 보면, 노드 2까지 가중치가 8임을 얻어온다.

노드 1을 거쳐서 2를 가는 것이 빠른지, 지금까지 업데이트 된 노드 2의 최단거리가 더 빠른지 비교하기 위해

D[1] + 8 과 D[2]를 비교한다. 지금은 D[2]가 무한대이므로, 더 작은 D[1]+8 값으로 업데이트 해준다.

 

다음 연결된 노드 3도 동일하게 작업하면 3으로 최단거리가 없데이트 된다.

 

 

 

5. 이후 3번과 4번을 반복해서 최단거리 배열을 완성한다

현재 노드 1을 방문하고 인접한 모든 노드들의 최단거리를 업데이트 해주었다.

다음으로 갈 노드를 선택할 때는, 이미 탐색한 노드 1은 제외하고 최단거리가 최소인 노드를 선택해준다.

그러면 노드 3이 선택되고, 노드 3과 연결된 노드를 탐색하여 최단거리를 업데이트해준다. (D[3]+13 = 16)

 

 

3번을 선택했으니, 다음에는 노드 2를 선택한다. (최단거리 8)

노드 2와 인접한 노드를 보니, 5와 4가 있다. 5는 현재 무한대이므로 무조건 D[2]+15로 업데이트 된다.

하지만 노드 4를 보면, 이전 노드 3에서 16으로 업데이트 되었다. 이번에는 노드 2를 거쳐서 4로가는 것과, 3을 거쳐서 가는 것을 비교해 준다. D[2]+4 = 12이므로, 노드 2를 거치는게 더 빠르다. 따라서 12로 다시 업데이트 해준다.

 

이렇게 반복하면 마지막 줄처럼 시작 노드에서 각 노드까지의 최단거리 배열이 완성된다.

 

 

한번 손으로 다른 예제를 풀어보았다.