회원가입

[그래프] 31. Dijkstra 알고리즘

NULL 2021-09-28

가중치 그래프에서 최단 경로를 구해주는 Dijkstra 알고리즘에 대해 본격적으로 알아보자.

 

Dijkstra 를 이용할 때는 distancepredecessor 그리고 complete 변수를 저장해 줘야한다.

distancepredecessor 는 표로 그리고 complete 변수는 Node의 색으로 나타내겠다.

 

알고리즘을 시작하기 전에는 각 Node까지의 경로가 있는지, 또 경로가 있으면 거리는 얼마나 되는지 이런 것을 다 모른다.

그렇기 때문에 모든 Nodedistance 는 무한대로 그리고 predecessorNone 으로 초기화 한다.

 

아직 방문한 Node 들도 없기 때문에 completeFalse로 초기화 한다.

지금 노란색 Node 들이 completeFalseNode 들이다.

 

시작 Node로 간다.

 

- distance 구하기

시작 Node 에서 시작 Node 자신까지의 거리는 0이다.

distance 를 0으로 설정해 준다.

 

- predecessor 구하기

마찬가지로 시작점에서 시작점까지의 경로는 자기 자신이다.

아무데서도 오지 않았기 때문에 predecessor 는 그냥 None 으로 두겠다.

 

- complete 구하기

complete 처리가 되지 않은 Node 중, 가장 distance 가 작은 Node 를 본다.

distance 가 0이 A 이다.

 

- relaxation 하기

그 다음에는 A엣지들을 볼 것이다.

이때 연결된 엣지NodecompleteNode면 건너 뛴다.

아직 complete 처리된 Node는 하나도 없기 때문에 엣지 (A, B)(A, C) 를 다 relax 해주면 된다.

relax 처리가 완료되면 complete 처리한다.

 

- relaxation 과정

(A, B)relax 하는 것을 보자.

Bdistance 는 무한대 이다.

Adistance 는 0 이다.

엣지의 가중치는 4 이다.

A distance + 엣지의 가중치 = 4 이다.

Bdistance 무한대보다 작으므로 distance 를 4 로 변경한다.

predecessorA로 바꿔줘야 된다.

 

(A, C)relax 를 해준다.

Cdistance 는 무한대 이다.

Adistance 는 0 이다.

엣지의 가중치는 1 이다.

A distance + 엣지 의 가중치 = 1 이다

Cdistance 무한대보다 작으므로 distance 를 1 로 변경한다.

predecessorA 로 바꿔준다.

 

이제 Acomplete 처리한다.

쉽게 생각해서 그냥 complete 변수를 True 로 바꾸는 것이다.

 

- 재시작

다음 시작으로 complete 되지 않은 Nodedistance 가 가장 작은 Node 를 고른다.

 

distance 가 1인 C 이다.

아까 했던 것 처럼 C엣지를 모두 relax 해준다.

이때 중요한 것은 completeNode엣지들은 무시한다.

 

AcompleteNode 이다.

건너 뛴다.

 

Bcomplete 되지 않았다.

(C, B)relax 해준다.

Bdistance 는 4

Cdistance 는 1

(C, B) 의 가중치는 2

C distance + (C, B) 가중치 = 3

C distance + (C, B) 가중치가 더 작으므로, Bdistance 는 3 그리고 predecessorC 로 바꾼다.

 

Dcomplete 되지 않았다.

(C, D)relax 한다.

Ddistance 는 무한대

Cdistance 는 1

(C, D)의 가중치는 1

C distance + (C, D) 가중치 = 2 는 Ddistance 무한대보다 작으니

DdistanceC distance + (C, D) 가중치 인 2이 되고, predecessorC 가 된다.

 

complete 되지 않은 인접한 모든 Node 를 돌았기 때문에 C 또한 complete 시킨다.

 

- 재시작

complete 되지 않은 Node 들 중에서 가장 distance 가 작은 것을 고른다.

distance 가 2인 D 이다.

 

D엣지를 모두 relax 시켜준다.

 

C 는 이미 complete 되어서 무시한다...

 

이런식으로 모든 Nodecomplete 시켜준다.

 

알고리즘이 종료된다.

 

- 최단 경로 찾기

모든 Nodepredecessor 를 저장하고 있다.

Dijkstra 알고리즘이 끝나면 distancepredecessor 변수가 확정된다.

 

만약 시작점으로부터 최단 거리를 알고 싶으면 Nodedistance 를 보면 된다.

최단 경로를 알고 싶으면 predecessor 를 이용해서 Backtracking 하면 된다.

 

- Backtracking

Backtracking 을 이용하여 최단 경로를 구해보자.

시작 Node A 에서 E까지의 경로를 알고 싶다고 가정하자.

 

E 에서 시작한다.

EpredecessorD 이다.

DpredecessorC 이다.

CpredecessorA 이다.

경로는 A - C - D - E 가 최단 경로이다.

 

최단 경로의 거리를 알고 싶으면 각 Nodedistance 를 보면된다.

 

Dijkstra 알고리즘을 일반화 해보자

 

Dijkstra 알고리즘 일반화


0 0