[Algorithm] Dijkstra (다익스트라)

다익스트라는 세마포어의 아버지시죠
- YG

최단 경로 알고리즘

다익스트라 알고리즘은 그래프의 특정 지점에서 다른 지점까지 최단 경로(효율적인 경로)를 구하는 알고리즘으로, 

각 지점은 그래프에서 노드로 표현하고 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 

 

그래프 알고리즘에서 대표적인 최단경로 알고리즘으로 다익스트라, 벨만-포드, 플로이드-워샬이 있는데,

다익스트라 알고리즘은 간선의 가중치가 하나라도 음수면 사용할 수 없다는 특징을 가지고 있다. 

(가중치가 음수일 경우 벨만-포드 알고리즘을 사용하면 되지만 현실적으로 음수일 경우가 없다고 한다)

 

간선의 가중치가 양수인데 서로 다를 때는 다익스트라!
간선이 모두 1일 때는 BFS 사용 가능!

 

매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하고 

하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리의 정보를 그대로 사용하기 때문에

다익스트라는 그리디이기도 하고 다이나믹 프로그래밍이기도 한다.

 

동작 과정

1. 출발 노드를 설정

2. 최단 거리 테이블 초기화 

3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산한 후 테이블 갱신

5. 3과 4번을 반복

 

 

[출처] https://techblog-history-younghunjo1.tistory.com/247

graph = {
    'A': {'B': 3, 'C': 6},
    'B': {'C': 1},
    'C': {'D': 1},
    'D': {'A': 7}
}

 

start가 A라고 가정하면,

다음과 같이 update를 하면서 진행한다.

 

import heapq

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  
  distances[start] = 0 
  
  queue = []
  heapq.heappush(queue, [distances[start], start])  

  while 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