[Algorithms] 다익스트라(Dijkstra)

다익스트라(Dijkstra)

• 문제 상황

  1. Va -> Vb까지의 최단경로
  2. Va -> 모든 노드 의 최단경로
  3. 모든 노드 -> 다른 모든 지점 의 최단 경로

• 그리디 알고리즘으로 분류됨

• 매 상황에서 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복

• 동작 단계

  1. 출발노드 설정
  2. 최단거리 테이블 초기화
  3. 현재 위치한 노드의 인접 노드들 중 방문하지 않은 노드들 중에서 가장 거리가 짧은 노드 선택. 그 노드를 방문 처리.
  4. cost를 계산하고 최단거리 테이블 업데이트
  5. (3)(4) 과정 반복

다익스트라 구현 방법

• 힙(Heap) 자료구조 이용
  

• cf) 힙(Heap)

  • 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조
  • Max Heap, Min Heap의 종류가 있음
    • 최대 힙을 최소 힙으로 쓰려면 저장되는 값에 -를 붙여 음수로 만들면 된다.
  • 삽입시간, 삭제시간: O(logN)
    

    import heapq
    heapq.heappush(myHeap, value)
    heapq.heappop(myHeap)

다익스트라 예제: 백준 1238번 파티 (파이썬)

import heapq
import sys

def dijkstra(start):
    distance = [INF] * (V+1)
    q = [] # 우선순위 큐
           # 현재 노드의 이웃들이 거리가 짧은 순으로 우선순위가 높게 담겨있음
     
    distance[start] = 0 # 시작점은 최단거리 0
    heapq.heappush(q, (0, start))

    while q: 
        # 큐에서 가장 최단거리가 짧은 노드 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면(더 짧은 최단거리가 이미 구해졌다면) 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for next in graph[now]:
            cost = dist + next[1]
            # 현재 노드를 거쳐서, 다음 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[next[0]]:
                distance[next[0]] = cost # 거리테이블 업데이트
                heapq.heappush(q, (cost, next[0]))
    return distance

input = sys.stdin.readline
INF = int(1e9) # 무한값(10억)

V, E, X= map(int, input().split())
graph = [[] for _ in range(V+1)]
 

# 모든 엣지값 입력받기
for _ in range(E):
    u, v, w = map(int, input().split())
    # u에서 v로 가는 가중치 w인 간선이 존재
    graph[u].append((v, w))


max_dist = 0
for i in range(1 ,V+1):
    # 다익스트라 i -> x
    d_0 = dijkstra(i)[X]
    # 다익스트라 x -> i
    d_1 = dijkstra(X)[i]
    max_dist = max(max_dist, d_0 + d_1)
    
print(max_dist)

(ref)
https://freedeveloper.tistory.com/277