[Algorithm] Dijkstra 다익스트라 최단 경로 알고리즘

 

다익스트라 알고리즘은 A에서 B까지의 최단 경로를 찾고자 할 때 사용한다.

 

 

먼저, 알고리즘을 직관적으로 살펴보자

 

다음과 같은 그래프에서 A->C로 가고자 할 때 최단 경로를 구해보자.

 

 

우선 출발지로부터 인접한 노드들과의 거리를 갱신한다. (빨간색)

 

 

그 다음 노드로 이동한다.

해당 노드에서 인접한 노드들 중에 방문하지 않은 노드들 과의 거리를 갱신한다.

다음과 같이 D의 거리가 5에서 3으로 갱신 되었다. (최단 거리)

 

 

C가 5에서 4로 갱신되었다.

 

 

현재 방문한 노드가 도착지라면 알고리즘을 종료한다.

 

 

그림처럼 A->C의 최단경로는 4가 된다. 위와 같이 동작하는 알고리즘이 다익스트라 알고리즘이다.

 

 

 

 

📌 Rule

1. 출발 노드로부터 인접한 노드들 사이의 거리를 갱신한다.

2. 다음 노드로 방문하여 인접 노드들 중 방문하지 않은 노드들 사이의 거리를 갱신한다.

3. 거리를 갱신할 때는 현재 거리가 저장되어 있는 거리보다 짧을 때만 갱신한다.

4. 2,3번 반복 후 도착지에 도착하면 알고리즘을 종료한다. (도착 노드에 저장된 거리가 최단거리)

 

 

 

 

Code

dic은 딕셔너리이다. key는 노드A value에는 [도착B, AB사이의 거리]가 리스트로 저장되어있다.

다음 코드는 양방향 그래프에서 l부터 r까지의 최단거리를 구하는 다익스트라 함수이다. 

import heapq

def dijkstra(n,l,r):
    cost=[float('inf') for x in range(n+1)]
    h=[(0,l)]
    cost[l]=0
    
    while h:
        cnt,num=heapq.heappop(h)
        if cost[num]<cnt:
            continue
            
        for i,j in dic[num]:
            if cnt+j<cost[i]:
                cost[i]=cnt+j
                heapq.heappush(h,(cnt+j,i))
                
    return cost[r]