Dijkstra 알고리즘

Dijkstra 알고리즘은 특정 Node를 시작점으로 하여, 해당 시작점부터 각 Node의 최단거리를 구하는 알고리즘입니다.

 

알고리즘은

1. 최초 시작점을 제외, 나머지 Node까지의 거리를 ∞로 설정한다.

2. 시작점에서 각 Node까지의 거리를 갱신

3. 시작점에서 가장 가까운 Node로 이동

4. 2~3을 반복하며, 더이상 이동할 Node가 없을때까지 반복

 

예시를 보면서 좀더 알아보겠습니다.

Kruskal 알고리즘을 포스팅 할때 사용한 숙련된 조교를 한번더 이용하겠습니다.

B Node를 시작점으로 진행하겠습니다.

B와 연결된 모든 Node와의 거리를 해당 Node의 Distance라고 설정하면

[5,0,11,7,8,2] <= B를 기준으로한 Distance List를 얻을 수 있습니다.

 

그 다음 B와 연결된 Node중 F가 2의 가중치로 가장 짧은것을 알 수 있습니다.

그럼 이제 Node F로 이동합니다.

빨간 네모는 Distance입니다

이제 F에서는 F의 Distance + F-인접 Node의 가중치를 인접Node의 Distance와 비교하여 최신화합니다.

Ex. C노드 의 경우

           F의 Distance = 2,    F-C의 가중치 = 1,    C의 Distance = 11

           F의 Distance + F-C의 가중치 = 2+1 <  C의 Distance = 11

따라서 C의경우 B-F-C를 통해서 이동하는 것이 더 짧은것을 알수 있습니다.

그럼 이제 C Node의 Distance를 3으로 최신화 해줍니다. 

============================================================================

이제 위 과정이, 더이상 나아갈 Node가 없을때까지 진행하면

 

B Node로부터 다른 Node의 최단거리를 구할 수 있습니다!

 

최종 B Node를 기준으로 최단거리 및 Distance

   

 

Dijkstra 알고리즘은 작은 문제에서 얻은 국소해를 바탕으로 Node간 최단거리를 구하는 알고리즘이 되겠습니다.

 

파이썬으로 구현된 Code입니다.

import copy
graph = [[0,5,4,6,10,2],
         [5,0,11,7,8,2],
         [4,11,0,8,3,1],
         [6,7,8,0,9,8],
         [10,8,3,9,0,2],
         [2,2,1,8,2,0]]


def dijkstra(init, DT_mat):            
    Max = len(DT_mat)
    #해당 Node 방문여부를 기록
    visit_history = [False for i in range(Max)]    
    Dist_list = copy.deepcopy(DT_mat[init])    
    is_not_end = True
    while is_not_end:                        
        candidate = copy.deepcopy(DT_mat[init])
        for j in range(len(candidate)):
            if candidate[j]==0:
                pass                
            elif candidate[j]+Dist_list[init]<=Dist_list[j]:
            	#Distance List의 값을 최신화해줍니다.
                Dist_list[j] = candidate[j]+Dist_list[init]                            
        min_value = 9999
        for i in range(len(Dist_list)):
            if Dist_list[i]<min_value and Dist_list[i]!=0 and i!=init and visit_history[i]==False:
                #그 다음 이동할 Node를 구합니다
                min_value = Dist_list[i]
                donext_node = i
        #Node의 방문여부를 최신화해줍니다.
        visit_history[init] = True
        DT_mat[donext_node][init] = 0
        DT_mat[init][donext_node] = 0
        init = donext_node
        #다음 Node가 방문한적이 있으면 알고리즘 종료
        if visit_history[init]==True:
            is_not_end = False
    return Dist_list


dijkstra(1, graph)

Out[72]: [4, 0, 3, 7, 4, 2]

아래는 Dijkstra알고리즘을 활용한 코딩테스트 문제입니다 :)

https://teus-kiwiee.tistory.com/102

그래프 - 가장 먼 노드