Dijkstra의 최단 경로 알고리즘

Dijkstra의 최단 경로 알고리즘

: 그래프에 노드가 여러 개 있을 때 특정 노드에서 다른 노드까지의 모든 최단 경로를 찾는 알고리즘

“지금까지 각 노드까지의 최단 거리” 정보는 1D 목록에 저장되며 더 짧은 거리가 발견되면 지속적으로 업데이트됩니다.

이 목록은 초기에 모두 “무한” int(1e9)로 초기화됩니다.

시행순서

실행 순서는 다음과 같습니다.

인기글

  1. 방문하지 않은 노드 중 방문 거리가 가장 짧은 노드를 선택합니다.
    이때 헷갈리지 말아야 할 한 가지는 ‘미방문’은 ‘원점 노드로부터의 최단 거리를 계산하지 않았다’는 뜻이거나 ‘이 노드를 통과할 때 이 노드에 연결된 다른 노드의 최단 거리를 계산하지 않음’방법
    즉, “타노드”를 방문할 때 계산된 “타노드”를 통과할 때 “자노드”까지의 최단 거리가 리스트에 저장되어 있어도 “자노드”를 방문한 것으로 간주하지 않는다. 이것은 ‘이 노드’를 방문하는 것이 아니라 ‘다른 노드’를 지날 때 ‘다른 노드’를 방문할 때의 최단 경로를 계산하는 것입니다.
  2. 현재 방문한 노드를 통해 도달 가능한 다른 노드를 확인하고, 현재 각 노드를 통한 최단 거리가 기존 목록의 값보다 작으면 업데이트합니다.

모든 노드를 방문할 때까지 이 작업을 반복합니다.

미방문 노드 중 거리가 가장 짧은 노드를 선택하는 경우, 선택된 노드는 ‘최단 거리’를 완전히 선택한 노드이며,

알고리즘을 더 반복해도 최단 거리가 줄어들지 않습니다.

따라서 각 단계에서 노드까지의 최단 거리는 확실히 발견됩니다.

즉, 선택한 노드의 최단 거리는 후속 단계에서 업데이트할 수 없습니다. 이후 단계에서는 해당 단계의 방문한 노드에 의해 계산되는 거리가 필연적으로 증가하기 때문입니다.

시간 복잡성 감소

1단계에서 “최단 거리 노드”를 선택하려면 목록을 다시 탐색해야 합니다.

Dijkstra의 알고리즘은 시작 노드를 제외한 모든 n-1 노드에 대해 반복되어야 합니다.

그 안에서 “최단 거리 노드”를 찾기 위해 목록을 다시 탐색하면

최악의 시간 복잡도는 O(V^2)입니다.

이것을 해결 더미 더미 데이터 구조사용

힙은 우선 순위 대기열을 구현하는 데 사용되는 데이터 구조입니다.

우선순위 큐예 우선순위가 높은 데이터부터 삭제하다.

따라서 위의 ‘최단 노드’를 선택하기 위해 최단 거리에 우선 순위를 설정하면 최단 노드가 순회하지 않고 자동으로 대기열에서 제외됩니다.

이를 별도로 구현할 필요가 없으며, 더미당신은 그것을 사용할 수 있습니다 (가치, 물건)우선 순위 대기열에 넣습니다.

Python의 기본 구조인 min-heap을 사용하면 값이 가장 작은 항목을 먼저 꺼냅니다.

이때 거리가 가장 짧은 노드를 뽑아야 하는 경우 heapq 라이브러리를 그대로 사용할 수 있다.

import heapq

queue = ()
heapq.heappush(queue, (0, start)) # 큐이름, (가치, 물건)
smallest = heapq.heappop(queue) # 알아서 (가치, 물건)의 가치가 가장 작은 물건을 꺼내줌

향상된 Dijkstra 알고리즘 소스 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())

# 시작 노드 번호 입력받기
start = int(input())

# 각 노드 연결 정보를 담은 그래프 리스트 만들기
graph = (() for i in range(n + 1)) # 인덱스 0은 무시, 1번 노드는 인덱스 1

# 최단 거리 테이블, 무한으로 초기화
distance = (INF) * (n + 1) # 인덱스 0은 무시, 1번 노드는 인덱스 1

# 그래프 리스트 채워넣기 (간선 정보 입력받기)
for _ in range(m):
	a, b, c = map(int, input().split())
    
    # a번 노드에서 b번 노드로 가는 거리는 c
    graph(a).append((b,c))
    


def dijkstra(start):
    q = ()
    heapq.heappush(q, (0, start)) # (거리, 노드번호)
    
    # 출발 노드에서 출발 노드까지 거리는 0
    distance(start) = 0
    
    while q: # 큐가 비어있지 않은 동안
    	
        # 최단 거리가 가장 짧은 노드 선택
    	dist, now = heapq.heappop(q)
        
        # 방문한 적 있는지 확인
        if distance(now) < dist: # 방문한 적이 있다면 리스트 값은 이미 최단 거리 확정
            continue
        
        # 연결된 노드들 거리 갱신
        for i in graph(now):   # i: (연결노드번호, 거리)
            cost = dist + i(1) # 현재 노드를 거쳐서 갈 경우의 최단거리
            
            # 현재 노드를 거쳐서 가는 것이 더 짧다면 갱신
            if cost < distance(i(0)):
            	distance(i(0)) = cost
                
                # 더 짧은 경로를 찾은 노드 정보들은 우선순위 큐에 넣는다
                heapq.heappush(q, (cost, i(0)))
 
dijkstra(start)

# 출력 - 각 노드로 가기 위한 최단 거리
for i in range(1, n + 1):
	if distance(i) == INF:
    	print("INFINITY")
    else:
    	print(distance(i))

과정은 힙을 사용하지 않을 때와 동일하나 힙을 통해 최단거리 노드를 선택하고 최단경로를 찾은 노드의 정보를 힙에 저장한다.

  1. 가장 짧은 거리의 노드를 방문하십시오(heapq.heappop(대기열)), 한 번도 방문한 적이 없는 노드가 맞습니다(기존 목록의 값 > 힙에서 방금 꺼낸 값) 확인하다.
  2. 현재 방문한 노드를 통해 도달 가능한 다른 노드를 확인하고, 현재 각 노드를 통한 최단 거리가 기존 목록의 값보다 작으면 업데이트합니다.

시간 복잡도는 O(ElogV)로 증가합니다.

error: Content is protected !!