다익스트라(Dijkstra) 알고리즘 _ 동작 과정

다익스트라(Dijkstra) 알고리즘

• 에츠허르 비버 데이크스트라(Edsger Wybe Dijkstra)가 1956년에 고안했으며 1959년에 발표

• 하나의 시작 정점에서 모든 다른 정점까지 최소비용의 인접정점을 선택하여 최단경로를 찾는 알고리즘

• 입력 그래프에서 간선들의 가중치가 모두 0 이상인경우에 쓰임, 음수 가중치는 지원되지 않음(벨만-포드 알고리즘은 음수 가중치 허용)

• 최단 경로는, 경로의 길이 순으로 정해짐

• 다이나믹 프로그래밍 문제(큰문제를 작은 문제로 나누어 푸는 문제)로 분류, 최단거리는 여러 개의 최단거리로 이루어져있기 때문이다

• 가중치를 계산해서 효율적인 것 부터 방문하는 알고리즘

• 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됨
  
  
  

다익스트라 알고리즘 순서

  1. 시작점을 기준으로 아직 방문하지 않았고 인접한 정점들까지의 최소 가중치 정리

  2. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

  3. 선별한 정점 방문, 방문한 정점 주변에 방문하지 않고 인접한 정점들을 파악

  4. 방문하지 않고 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

5. (전체 정점 개수 - 1(시작점)) 회 만큼 2~4 과정 반복

 

 

 

 

다익스트라 알고리즘 동작 과정 파헤치기

1. 시작 정점을 기준으로 모든 정점에 이르는 최소 가중치(최단거리)를 구해본다 이때 인접한 정점들은 가중치 계산이 되지만, 인접하지 않은 정점들은 어떤 점들을 경유해서 가야 될텐데, 아직 어떤점들을 지나갈지 모르므로 가중치가 무한(0이 아닌 모든 가중치들의 합보다 큰 일정한 하나의 수)이라고 한다.

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

INF

8

INF

INF

6

10

INF

INF

INF

INF

INF

A_A는 A에서 A까지 도달하는 거리므로 사실상 0과 다름없다.

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

 

 

 

 

 

 

2. 인접한 정점들중 제일 낮은 가중치를 가진 정점(해당 예시에서는 G = 6)을 방문처리 한다.

3. 방문한 정점을 기준으로 다시 인접하며, 아직 방문하지 않은 정점들을 찾는다,

이때 아까 인접하지 않았서 가중치를 무한으로 했던 정점들도 발견할 수 있는데, 지금 기준 정점(지금까지 제일 낮은 가중치)을 경유하여 오게 되므로, 지금 기준 정점까지의 최소 가중치 + 해당 정점들 까지의 가중치 와 현재 기록되있는 최소가중치와 비교하여 더 빠르면 기입하고, 빠르지 않으면 그대로 둔다.

 

A_F = INF > A_G(6) + G_F(8) ? A_G(6) + G_F(8) : A_F(INF); //바뀜

A_H = 10 > A_G(6) + G_H(6) ? A_G(6) + G_H(6)  : A_H(10); //바뀜

A_M = INF > A_G(6) + G_M(7) ? A_G(6) + G_M(7) : A_M(INF); //바뀜

 

 

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

INF

8

INF

14

6

10

INF

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

 

 

 

 

 

 

 

 

 

4. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

 

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

INF

8

INF

14

6

10

INF

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

 

위표를 기준으로 D가 제일 작고, 방문하지 않았으므로 D가 선택됐다.

 

5. 선별한 정점(D) 방문, 방문한 정점 주변에 인접한 정점들을 파악

6. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

A_E = A_E(INF) > A_D(8) + D_E(10) ? A_D(8) + D_E(10) : A_E(INF); //바뀜

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

INF

8

18

14

6

10

INF

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

 

 

 

 

 

 

 

7.최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

INF

8

18

14

6

10

INF

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

B가 선택됐다.

 

8. 선별한 정점(B) 방문, 방문한 정점 주변에 인접한 정점들을 파악

9. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_C = A_C(INF) > A_B(9) + B_C(8) ? A_B(9) + B_C(8) : A_C(INF); //바뀜

 

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

INF

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

 

 

 

 

 

 

10. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

INF

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

H가 선택됐다

 

11. 선별한 정점(H) 방문, 방문한 정점 주변에 인접한 정점들을 파악

12. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

A_I = A_I(INF) > A_H(10) + H_I(10) ? A_H(10) + H_I(10) : A_I(INF); // 바뀜

 

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

 

 

 

 

 

 

 

 

13. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

INF

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

M이 선택됐다

 

14. 선별한 정점(M) 방문, 방문한 정점 주변에 인접한 정점들을 파악

15. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

A_I = A_I(20) > A_M(13) + M_I(13) ? A_M(13) + M_I(13) : A_I(20) // 그대로

 

A_L = A_L(INF) > A_M(13) + M_L(7) ? : A_M(13) + M_L(7) : A_L(INF) // 바뀜

 

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

20

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

 

 

 

 

 

 

 

16. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

20

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

F 가 선택됐다

 

17. 선별한 정점(F) 방문, 방문한 정점 주변에 인접한 정점들을 파악

18. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

A_E = A_E(18) > A_F(14) + F_E(7) ? A_F(14) +F_E(7) : A_E(18) // 그대로

 

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

20

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

 

 

 

 

 

 

 

19. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

20

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

C가 선택됐다.

 

20. 선별한 정점(C) 방문, 방문한 정점 주변에 인접한 정점들을 파악

21. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

A_I = A_I(20) > A_C(17) + C_I(7) ? A_C(17) + C_I(7) : A_I(20) // 그대로

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

20

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

 

 

 

 

 

 

 

 

 

22. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로

A_A

A_B

A_C

A_D

A_E

A_F

A_G

A_H

A_I

A_J

A_K

A_L

A_M

가중치

0

9

17

8

18

14

6

10

20

INF

INF

20

13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

E로 선택됐다.

 

 

23. 선별한 정점(E) 방문, 방문한 정점 주변에 인접한 정점들을 파악

24. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

A_J = A_J(INF) > A_E(18) + E_J(11) ? A_E(18) + E_J(11)  : A_J(INF) // 바뀜

 

 

경로	A_A	A_B	A_C	A_D	A_E	A_F	A_G	A_H	A_I	A_J	A_K	A_L	A_M
가중치	0	9	17	8	18	14	6	10	20	29	INF	20	13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

 

 

 

25.최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로	A_A	A_B	A_C	A_D	A_E	A_F	A_G	A_H	A_I	A_J	A_K	A_L	A_M
가중치	0	9	17	8	18	14	6	10	20	29	INF	20	13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

※I 와 L 둘다 안방문 했으면서, 그중에서 제일 작은 가중치 20을 동일하게 나타내고 있다, 이럴때는 for문과 배열을 사용한다는 것을 감안하여 순차적으로 I부터 방문한다

 

 

 

26.선별한 정점(I) 방문, 방문한 정점 주변에 인접한 정점들을 파악

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

O

 

 

27.인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

 

※인접하면서 아직 방문하지 않은 정점이 주변에 하나도 없으므로 과정이 생략된다(반복문 안에 조건문을 만족시키지 못하고 계속 continue 되어 결국 반복문이 끝나고 다음 순서, 최소 가중치 정점 선별로 넘어가 버린다.)

 

 

 

 

 

 

 

28.최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로	A_A	A_B	A_C	A_D	A_E	A_F	A_G	A_H	A_I	A_J	A_K	A_L	A_M
가중치	0	9	17	8	18	14	6	10	20	29	INF	20	13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

O

L 이 선택됐다.

 

29. 선별한 정점(L) 방문, 방문한 정점 주변에 인접한 정점들을 파악

30. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

A_K = A_K(INF) > A_L(20) + L_K(7) ? A_L(20) + L_K(7)  : A_K(INF) // 바뀜

경로	A_A	A_B	A_C	A_D	A_E	A_F	A_G	A_H	A_I	A_J	A_K	A_L	A_M
가중치	0	9	17	8	18	14	6	10	20	29	27	20	13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

O

O

 

 

 

 

 

 

31. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로	A_A	A_B	A_C	A_D	A_E	A_F	A_G	A_H	A_I	A_J	A_K	A_L	A_M
가중치	0	9	17	8	18	14	6	10	20	29	27	20	13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

O

O

K가 선택됐다.

 

 

32. 선별한 정점(K) 방문, 방문한 정점 주변에 인접한 정점들을 파악

33. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_J = A_J(29) > A_K(27) + K_J(9) ? A_K(27) + K_J(9)  : A_J(29) // 그대로

 

 

 

 

 

 

 

34. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

경로	A_A	A_B	A_C	A_D	A_E	A_F	A_G	A_H	A_I	A_J	A_K	A_L	A_M
가중치	0	9	17	8	18	14	6	10	20	29	27	20	13

 

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

O

O

O

J가 선택됐다.

 

35. 선별한 정점(J) 방문, 방문한 정점 주변에 인접한 정점들을 파악

정점

A

B

C

D

E

F

G

H

I

J

K

L

M

방문

O

O

O

O

O

O

O

O

O

O

O

O

O

 

36. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

※인접하면서 아직 방문하지 않은 정점이 주변에 하나도 없으므로 과정이 생략된다(반복문 안에 조건문을 만족시키지 못하고 계속 continue 되어 결국 반복문이 끝나고 다음 순서, 최소 가중치 정점 선별로 넘어가 버린다.)

 

 

 

 

37. 해당 그래프를 기준으로 여기까지 하면 총 11회 방문, 즉 정확히 전체정점 개수(12) - 1 만큼,  아래 과정을 반복하게 된다.

 

1. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별
2. 선별한 정점 방문, 방문한 정점 주변에 인접한 정점들을 파악
3. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠
   • (현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

 

 

 

 

알고리즘이 종료 되면, 지금까지 초기화 시켰던 최소 가중치 정리 배열에는 시작점(A)로 부터 각각 정점까지 가는데 드는 최소 비용을 정리해 놓게 된다.

경로	A_A	A_B	A_C	A_D	A_E	A_F	A_G	A_H	A_I	A_J	A_K	A_L	A_M
가중치	0	9	17	8	18	14	6	10	20	29	27	20	13

예를들면 A(시작점) 에서 정점 K 까지 간다고 했을때, A -> D -> E  -> J -> K로 거쳐서 갈 수도 있겠지만

가중치 크기 비교를 하면

A -> G -> M -> L -> K( A_G + G_M + M_L + L_K )가  A -> D -> E  -> J -> K(A_D + D_E + E_J + J_K) 보다 작다,

 

즉 더 빠르게 갈 수 있다는 뜻이고, 이렇게 다양한 정점들 속에서 나올 수 있는 최소비용, 즉 최단거리들을 기록해 놓은 것이 위의 표이고, 곧 지금까지의 과정 Dijkstra 알고리즘을 통해서 구할 수 있는 것이다.

 

 

지하철 노선도 앱 최단 경로 탐색