[알고리즘] 탐욕법 - 다익스트라 알고리즘 (Greedy Approach - Dijkstra's Algorithm)

다익스트라 알고리즘은 단일 출발점에서의 최단 경로의 문제를 푸는 알고리즘입니다.

 

앞선 DP 알고리즘에서 Floyd's Algorithm을 이용해서 모든 출발점에서의 최단 경로의 문제를 풀었습니다.

하지만 하나의 특정 vertex에서 다른 모든 vertex로 가는 최단 경로만 알고 싶다면 프로이드의 알고리즘은 너무 과합니다.

 

시작하기에 앞서 프로이드의 알고리즘은 n^3인 것에 반해, 다익스트라 알고리즘은 n^2입니다.

 

다익스트라 알고리즘은 Prim's Algorithm과 매우 흡사합니다.

 

• 집합 Y를 최단 경로를 구하려고 하는 vertex만 포함한다. (v_1이라고 함) 그리고 F는 공집합으로 초기화한다.
• v_1과 가장 가까운 vertex를 찾아서, 이 vertex를 Y에 포함하고, edge를 F에 포함한다.
• 다음 v_1에서 Y에 속한 vertex를 거쳐서 V-Y로 가는 가장 가까운 vertex를 찾습니다.
  • 이 부분이 Prim's Algorithm과 다름
• 이후 Y가 V와 같아질 때까지 반복합니다.

 

슈도 코드는 다음과 같습니다.

Y = v_1
F = 0

while the instance is not solved:
	select a vertex v from V-Y that has a shortest path from v_1,
    using only vertices in Y as intermediates
    
    add the new vertex v to Y
    add the edge that touches v to F
    
    if Y == V:
    	the instance is solved

 

프림 알고리즘과 매우 흡사하지만, 프림 알고리즘은 nearst와 distance를 사용하는데 반해, 다익스트라 알고리즘은 touch와 length를 사용합니다.

 

i = 2부터 시작할 때,

• touch[i] = Y에 속한 vertex만을 이용하여 v_1에서 v_i로 갈 때, v_i에 가기전 마지막으로 거치는 vertex
• length[i] = Y에 속한 vertex만을 이용하여, v_1에서 v_i로 가는 최단 거리

 

예전에 공부했던 자료인데 이해가 가시나요?

 

노란색인 빈칸은 교수님이 가리신거라,,,ㅎㅎ;;;

 

암튼 감사합니다.

 

 

지적 환영합니다.