djikstra 알고리즘

djikstra 알고리즘

백준 1753번을 풀면서 djikstra 알고리즘(다익스트라 알고리즘) 개념에 대해서 다시 한 번 정리해봤다. djikstra 알고리즘은 최단 경로 탐색 알고리즘 이다. 시작 정점에서 모든 정점으로 가는 최단 경로를 알려주는데, 전체적인 로직은 다음과 같다.

1.출발 정점을 기준으로 각 정점까지의 최소 비용을 저장한다.
2.방문하지 않은 정점 중에서 가장 비용이 적은 정점을 선택한다.
3.해당 정점을 거쳐서 특정 정점으로 가는 경우와, 현재 저장되어있는 경우를 비교하여 최소 비용을 갱신한다.

예를들어, 1->3으로 바로 가는 방법의 비용은 5이고, 1->2->3으로 가는 방법의 비용은 3일 수 있는 것이다. 이러한 부분들을 고려하여 시작 노드에서 각 노드까지의 모든 최소 비용을 구하는 것이 djikstra 알고리즘이다. 구현은 위의 로직 그대로 하면된다. 다만, 가장 비용이 적은 로직을 선택하기 때문에, python에서는 heapq (최소 힙 방식을 사용한다.) 를 이용하여 구현하면 편리할 것이다. heapq를 이용하면 djikstra를 다음과 같은 방식으로 구현할 수 있다.

def dijkstra(start):
  q=[]
  heapq.heappush(q,(0,start)) #시작정점-시작정점은 0
  distance[start] = 0 #distance:거리를 저장하는 배열

  while q:
      dist, now = heapq.heappop(q)
      if distance[now] < dist:
          continue
      for i in graph[now]: #graph:각 간선 별 가중치 저장하는 배열 (정점, 가중치) 방식으로 저장됨.
          cost = dist + i[1]
          if cost<distance[i[0]]:
              distance[i[0]] = cost
              heapq.heappush(q,(cost,i[0]))