최단거리 (improved_dijkstra)

improved_dijkstra

간단한 다익스트라는 O(v^2)의 시간복잡도를 가져 노드의 개수가 10000개를 넘어가면 풀수가 없다.


하지만 개선된 다익스트라는 최악의 경우에도 O(ElogV)를 보장하여 해결할 수 있다. (V는 노드의 개수, E는 간선의 개수)


기존 간단한 다익스트라는 최단거리를 앞에서부터 하나씩 확인했는데 이를 더욱 빠르게 heap구조의 우선순위 큐로 찾는다는것이 핵심 포인트이다.

• 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 특징이 있고 heapq 라이브러리를 통해 사용한다.
• 우선 순위 큐는 일반적으로 정수형 자료형의 변수를 사용하며 (가치, 무게)로 이루어진 데이터를 우선순위 큐에 집어넣으면 항상 가치가 높은 물건부터 먼저 나오게된다.(만약 (무게, 가치)로 이루어진 데이터라면 무게가 높은 순으로 나오게 된다.)(최대힙을 사용한다고 가정)
• 파이썬에서는 기본값으로 최소힙구조를 사용하는데, 다익스트라는 최단거리는 구하는것이므로 최소힙을 그대로 사용하면된다.

간단한 다익스트라에서 '최단 거리가 가장 짧은 노드를 선택하는 함수'를 우선순위 큐로 대체

---

import heapq
import sys
input = sys.stdin.readline    # 입력데이터가 많다는 가정하에 빠른 입력을 받는 내장함수 사용
INF = int(1e9)  #무한을 나타내는 값으로 10억 설정

n, m = map(int, input().split())   #노드의 개수, 간선의 개수
start = int(input())    # 시작 노드번호
graph = [[] for i in range(n + 1)]  # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
distance = [INF] * (n + 1)     # 최단 거리 테이블을 모두 무한대로 초기화

for _ in range(m):      # 노드들 간 연결 유무와 간선의 비용 입력
  a, b, c = map(int, input().split())
  graph[a].append((b,c))        # a번 노드에서 b번 노드로 가는비용이 c라는 의미

def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))     # 시작노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입 (노드와 경로의 크기가 바뀜(heap은 앞에 인자를 기준으로 최소를 찾기 때문에))
  distance[start] = 0
  while q:    # 큐(q)가 비어있지 않다면
    dist, now = heapq.heappop(q)    # 가장 최단거리가 짧은 (가장앞에있는) 노드에 대한 정보를 꺼내어 dist, now에 저장(경로크기, 노드)
    if distance[now] < dist:        # 현재 노드가 이미 처리된적 있는 노드라면 무시
      continue
    for i in graph[now]:            # 현재 노드와 연결된 다른 인접한 노드들을 확인
      cost = dist + i[1]
        if cost < distance[i[0]]:   # 만약 현재 노드를 거쳐 다른 노드로 이동하는 거리(dist + graph(1))가 더 짧은 경우 업데이트 
        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])