Dijkstra

다익스트라(Dijkstra) 알고리즘이란 특정 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 탐색할 때 사용하는 알고리즘이다.

가중치 그래프

가중치 그래프는 아래와 같이 그래프에 각 간선(edge) 마다 가중치(weight)를 추가한 것입니다. 예를 들어 A에서 B로 가는 데 3의 비용이 든다고 생각하면 됩니다.

코드로는 아래와 같이 그래프와 동일하게 표현하는 대신 각 간선의 가중치를 추가해서 기록해준다.

다익스트라 구현

import heapq
 
graph = {
  1: [[2, 2], [1, 4]],
  2: [[1, 3], [9, 5], [6, 6]], 
  3: [[4, 6]],
  4: [[3, 3], [5, 7]],
  5: [[1, 8]],
  6: [[3, 5]],
  7: [[7, 6], [9, 8]],
  8: []
}
 
def dijkstra(graph, start, final):
  costs = {}
  pq = []
  heapq.heappush(pq, [0, start])
 
  while pq:
    cur_cost, cur_v = heapq.heappop(pq)
    if cur_v not in costs:
      costs[cur_v] = cur_cost
      for cost, next_v in graph[cur_v]:
        next_cost = cur_cost + cost
        heapq.heappush(pq, [next_cost, next_v])
 
  return costs[final]
 
print(dijkstra(graph, 1, 8))

Dynamic Programming MST