[알고리즘] 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘

• 최단경로를 찾는 알고리즘 중 양의 가중치만이 있는 그래프만을 취급
• 특정 위치에서 도착위치의 최단경로를 찾는 알고리즘(모든경로의 최단경로를 구하지는 않는다.
• 그리디하게 정점을 선택해 방문. 선택한 정점의 인접정점 중 방문되지 않은 것들에 대해 최단경로를 구해가며 도착지점에 도달.
• 배열에 각각 노드에 접근 시 가중치 합을 저장하며 지나간다.

• 0번 노드에서 출발해서 방문하지 않은 인접한 노드 중에 가중치가 가장 적은 노드에 대해 방문한다.
• 현재 그리디하게 선택한 경로의 가중치 합이 나중에 최단 경로가 아닐 수도 있으니 배열에 가중치의 합들을 저장하며 지나간다

• 1번 노드에서 인접한 노드 중 가중치가 제일 작은것은 4번이다.
• 이 때, 비교해봐야하는 것은 0번 노드에서 4번노드로 가는 경로 중 현재 선택된 경로보다 가중치가 적은 경로가 있는지 확인해야 한다.
  • 현재 0 -> 1 -> 4와 비교를 하기 위해서는 0 -> 3 -> 4의 가중치를 알아야한다.
  • 이를 우선순위 큐를 이용해서 누적 가중치가 적은것부터 뽑아내는 것으로 해결한다.

• 마지막으로 4번노드에서 6번노드로 이동하면 총 가중치가 1 + 1 + 2로 최단경로를 구할 수 있다.

구현 논리

1. 출발 노드와, 도착 노드를 설정
2. 알고 있는 모든 거리 값을 부여
3. 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리를 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다.
4. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다.
5. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다.

우선 순위 큐(heapq)

• O(log n)

아무 것도 없는 list에 heap

import heapq

h = []
heapq.heappush(h, 3)    # 첫 번째 파라미터에는 list 객체가
heapq.heappush(h, 9)    # 두 번째 파라미터에는 삽입하려는 객체가 들어간다.
heapq.heappush(h, 7)
heapq.heappush(h, 8)
heapq.heappush(h, 5)
heapq.heappush(h, 1)

for _ in range(6):
    print(heapq.heappop(h))    # 작은 값부터 출력된다.

최대 힙

import heapq

h = []
heapq.heappush(h, -3)    # 첫 번째 파라미터에는 list 객체가
heapq.heappush(h, -9)    # 두 번째 파라미터에는 삽입하려는 객체가 들어간다.
heapq.heappush(h, -7)    # 단, 원래 넣으려는 값에 -를 붙여주고
heapq.heappush(h, -8)    # 출력시에도 -을 붙여준다.
heapq.heappush(h, -5)
heapq.heappush(h, -1)

for _ in range(6):
    print(-heapq.heappop(h))    # 큰 값부터 출력된다.

기존 list 힙으로 정렬하기.

import heapq

h = [3, 9, 1, 4, 2]
heapq.heapify(h)    # 파라미터로 list 객체를 받는다.

for _ in range(6):
    print(-heapq.heappop(h))    # 작은 값부터 출력된다.

---

예시 코드

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq  # 우선순위 큐 구현을 위함

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
  distances[start] = 0  # 시작 값은 0이어야 함
  queue = []
  heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작 하기 위함.

  while queue:  # queue에 남아 있는 노드가 없으면 끝
    current_distance, current_destination = heapq.heappop(queue)  # 탐색 할 노드, 거리를 가져옴.

    if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음
      continue

    for new_destination, new_distance in graph[current_destination].items():
      distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
      if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
        distances[new_destination] = distance
        heapq.heappush(queue, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입

  return distances

print(dijkstra(graph, 'A'))

# {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}