[Python] 다익스트라 - JuyeolRyu/CodingTest GitHub Wiki

1. 다익스트라(Dijkstra)

  • 그래프에서 하나의 출발점에서 다른 노드들까지 최단거리를 구하는 알고리즘입니다.
  • 양방향 단방향 상관 없지만 간선의 값이 양수여야 합니다.(음수의 경우 밸만 포드 알고리즘 사용)
  • 우선순위 큐를 사용해서 간선의 길이가 작은 경로부터 탐색합니다.

2. 다익스트라(Dijkstra) 풀이 과정

  • 출발지점을 제외한 나머지 노드들의 거리는 무한대(INF)로 초기화합니다.
    image
  • 반복문을 돌면서 인접 노드를 방문하고 이전 dist값보다 작으면 값을 변경해줍니다.
    image
  • 위의 과정을 큐가 빌때까지 반복해줍니다.

3. 다익스트라(Dijkstra) 예시

import sys
import heapq
from collections import defaultdict

def dijk(g,s):
    #make distance dictionary and init
    dist = defaultdict(int)
    for node in range(1,n+1):
        dist[node] = float('inf')
    dist[s] = 0

    #search dist
    q = []
    heapq.heappush(q,[dist[s],s])
    while q:
        cur_cost,cur_node = heapq.heappop(q)

        for ne_node,ne_cost in g[cur_node]:
            cost = dist[cur_node]+ne_cost
            if cost < dist[ne_node]:
                dist[ne_node] = cost
                heapq.heappush(q,[cost,ne_node])
    return dist

#input value
n = int(input())
m = int(input())
graph = defaultdict(list)

for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append([b,c])

start,end = map(int,input().split())
ans = dijk(graph,start)

4. 다익스트라(Dijkstra) 문제

◼ 최소비용 구하기
◼ 특정한 최단경로