그래프의 최소 비용 문제

1. 최소 신장 트리(MST, Minimum Spanning Tree) 구하기

   • 크루스칼(Kruskal) 알고리즘
     : 간선이 적고 노드가 많을 때 유리하다.
   • 프림(Prim) 알고리즘
     : 간선이 많을 때 유리하다.

2. 최단 경로 구하기

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

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

그리디(Greedy) 알고리즘 사용

특징

프림 알고리즘과 유사하다.
음의 가중치가 존재할 경우에는 사용할 수 없다. 만약 음의 가중치가 존재한다면 벨만-포드(Bellman-Ford) 알고리즘을 사용하는 것이 좋다.

방법

시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식

1. 시작 정점을 선택한다.
2. 선택한 정점을 선택된 정점 집합에 추가한다.
3. 선택된 정점 집합에 연결된 간선들 중 선택되지 않은 노드와 연결되고, 그 중에서 가장 짧은 거리를 가진 간선과 연결된 다음 정점을 선택한다.
4. 목표 정점이 선택될 때까지 2~3 과정을 반복한다.

코드

def Dijkstra(depart, dest, graph):
  visited = [] # 정점(index)이 선택되었는지 여부 저장
  min_distances = [] # 시작 정점에서 해당 정점(index)로 올 수 있는 최단 거리
  
  min_distances[depart] = 0 # 시작점-시작점 거리이므로 0으로 세팅
  
  # 정점 개수만큼 반복한다.
  for _ in graph:
    # 1. 선택되지 않은 정점 중 최소의 거리로 갈 수 있는 정점을 찾는다.
    for node in graph:
      if not visited[node] and min_distance > min_distances[node]:
        min_distance = min_distances[node]
        min_node = node
    
    # 2. 찾은 정점을 선택된 정점 집합에 추가한다(포함시킨다).
    visited[min_node] = true;
    
    # 4. 선택된 정점이 목표 정점이면 최단 거리를 구했다.
    if min_node == dest:
      break
    
    # 3. 찾은 정점을 경유지로 해서 선택되지 않은 타 정점과의 거리 정보를 최소로 업데이트한다.
    for node, distance in graph[min_node]:
      # (출발지 ~ 선택된 정점 ~ 타 정점) 과 이미 저장된 (출발지 ~ 타 정점) 거리 값을 비교해 작은 값으로 업데이트한다.
      if not visited[node] and min_distances[min_node] + distance < min_distances[node]:
        min_distances[node] = min_distances[min_node] + distance
        
  return min_distances[dest]

최적화

BFS와 우선순위 큐(또는 최소 힙)를 사용해, 다음으로 갈 정점을 찾는 과정을 더 빠르고 쉽게 구할 수 있다.

최적화한 코드

import heapq

def Dijkstra(depart, dest, graph):
  visited = [] # 정점(index)이 선택되었는지 여부 저장
  min_distances = [] # 시작 정점에서 해당 정점(index)로 올 수 있는 최단 거리
  min_heap = [] # 최소 힙
  
  min_distances[depart] = 0 # 시작점-시작점 거리이므로 0으로 세팅
  heapq.heappush((0, depart)) # 최소 힙에 (거리, 정점) 형식으로 시작 정점 추가
  
  # 힙에 방문할 정점이 남아있는 동안 반복한다.
  while min_heap:
    # 1. 선택되지 않은 정점 중 최소의 거리로 갈 수 있는 정점을 찾는다.
    min_distance, min_node = heapq.heappop()
    
    # 만약 찾은 정점이 이미 방문했던 정점이라면 아래 업데이트 과정을 수행하지 않는다.
    if visited[min_node]:
      continue
    
    # 2. 찾은 정점을 선택된 정점 집합에 추가한다(포함시킨다).
    visited[min_node] = true;
    
    # 4. 선택된 정점이 목표 정점이면 최단 거리를 구했다.
    if min_node == dest:
      break
    
    # 3. 찾은 정점을 경유지로 해서 선택되지 않은 타 정점과의 거리 정보를 최소로 업데이트한다.
    for node, distance in graph[min_node]:
      # (출발지 ~ 선택된 정점 ~ 타 정점) 과 이미 저장된 (출발지 ~ 타 정점) 거리 값을 비교해 작은 값으로 업데이트한다.
      if not visited[node] and min_distances[min_node] + distance < min_distances[node]:
        min_distances[node] = min_distances[min_node] + distance
        heapq.heappush(min_heap, (min_distances[node], node))
        
  return min_distances[dest]

이미 방문했던 정점을 선택하지 않는 이유?

최소 힙에는 거리값이 업데이트될 때마다 추가하기 때문에 중복된 정점이 들어갈 수 있다.
예를 들어 거리 11의 값으로 3번 정점이 먼저 추가된 뒤, 거리 10의 값으로 업데이트되며 또 추가되면
최소 힙에서 거리 10의 3번이이 먼저 나온 뒤 나중에 거리 11의 3번이 나오게 된다.
하지만 거리 11인 3번 정점이 나와도 인접 정점을 확인하며 거리가 더 작이 갱신되는 경우는 있을 수 없기에, 방문한 정점의 인접 정점은 확인할 필요가 없다.