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

최단 경로 알고리즘 중 가장 많이 사용된다고 할 수 있는 다익스트라 알고리즘에 대해서 알아보자

 

• 특징 : 무방향 그래프, 방향 그래프에 모두 적용 가능하다.
• 가정 : 모든 간선은 음이 아닌 비용을 가진다.

 

■ 다익스트라 알고리즘의 Concept

• 시작 정점 ~ 모든 다른 정점까지의 최단 경로를 구한다.
• 시작 정점 v에서 정점 u까지의 최단경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 정점 u에 의해 단축되는 경로가 있는지를 반복적으로 확인한다.
• 현재 알고 있는 dist[w]와 새로 추가된 정점 u를 거쳐가는 dist[u] + cost[u][w]를 비교해 더 단축된 작은 값을 새로운 dist[w]로 가중치를 수정한다.

 

dist

    A           B           C          D           E

0

10

5

∞

∞

pred

     A            B           C          D           E

A

A

 

 

이와 같은 초기 상태를 가진 경로가 있다고 가정해 보자. 이를 통해 끊임없이 dist와 pred를 수정한다.

 

1) dist 중 가장 작은 값을 가진 C 지점을 정점 u라 지정하고 S집합에 추가한 S = {A, C} 상태에서 A와 C를 제외한 경로를 체크한다.

min{ dist[B], dist[C] + cost[C][B] } = min {10, 5+3} = 8 → dist[B]

min{ dist[D], dist[C] + cost[C][D] } = min {∞, 5+9} = 14 → dist[D]

min{ dist[E], dist[C] + cost[C][E] } = min {∞, 5+2} = 7 → dist[E]

 

dist

    A           B           C          D           E

0

8

5

14

7

 

pred

     A            B           C          D           E

C

A

C

C

 

2) dist 중 이미 거친 A,C를 제외한 정점 중 가장 작은 값을 가진 E 지점을 정점 u라 지정하고 S집합에 추가한 S={A,C,E} 상태에서 A, C, E를 제외한 경로를 체크한다.

 

min{ dist[B], dist[E] + cost[E][B] } = min {8, 경로X} = 8 → dist[B]

min{ dist[D], dist[E] + cost[E][D] } = min {14, 7+6} = 13 → dist[D]

 

dist

    A           B           C          D           E

0

8

5

13

7

 

pred

     A            B           C          D           E

C

A

E

C

 

3) dist 중 이미 거친 A,C,E를 제외한 정점 중 가장 작은 값을 가진 B 지점을 정점 u라 지정하고 S집합에 추가한 S={A,C,E,B} 상태에서 A,C,E,B를 제외한 경로를 체크한다.

 

min{ dist[D], dist[B] + cost[B][D] } = min {13, 8+1} = 9 → dist[D]

 

dist

    A           B           C          D           E

0

8

5

9

7

pred

     A            B           C          D           E

C

A

B

C

 

4) 집합 S에 마지막 경로인 D가 추가되면서 S={A,C,E,B,D}이고 dist = {0,8,5,9,7}, pred = { ,C,A,B,C}로 최단 경로가 완성된다. 

 

 

 

위에서 설명한 경로를 코드로 옮겨 보았다.

• 가중치가 가장 작은 정점(노드)을 선택하는 함수 : select_next 함수
• 다익스트라 알고리즘 : shortest_path_D 함수

■ shortest_path_D 함수 설명

1) 두번째 for문에서 path_mincost 변수에 cost 가중치 값이 무한대가 아니면 시작점을 넣고, 아니면 null로 처리한다.

(path_mincost 변수는 위에서 설명한 pred이다.

2) 세번째 for문에서 경로가 없으면 의미없는 값 -1을 담고, 경로가 있으면 s[u]에 true값 1을 담는다. u == -1이 되면 방문할 곳이 없으므로 break로 처리한다.

3) 네번째 for문에서 다익스트라 알고리즘 수식을 계산하고 새로운 가중치 계산이 기존 가중치 계산 보다 더 작게 될 때 dist[w]에 새로운 가중치값을 담아주고 path_mincost 변수를 새로운 정점 u로 담아준다.

 

■ 메인함수

메인함수에서 위에서 정의한 shortest_path_D를 cost값으로 정해주고 A~D의 최종 cost는 9라는 값을 도출해 낼 수 있다. 

 

=> 손으로 푼 값과 코드로 도출해 낸 결과값이 같음을 볼 수 있다.

 

이렇게 Dijkstra Algorithm을 알아보았다. 최단 경로 알고리즘 중 가장 많이 쓰이고 유명한 알고리즘이므로 잘 기억해 두자.