최단경로 - (1) 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘

다익스트라 알로리즘은 그래프에서 최단 경로를 찾는 알고리즘 중 하나로, 하나의 출발점을 기준으로 다른 모든 정점까지의 최단 거리를 구할 때를 활용할 수 있는 알고리즘이다.

다익스트라 알고리즘 구현

다익스트라 알로리즘은 최단 거리를 찾기 위해 시작 정점에서부터 인접한 정점들을 하나씩 방문하며 해당 정점까지의 거리를 갱신해 나간다. 인접한 정점들을 하나씩 방문한다는 점에서 BFS와 유사하지만, 동시에 해당 정점들까지의 거리를 갱신해나가야 하기 때문에 몇 가지 자료구조가 더 필요하다.

• 시작 정점부터 다른 정점까지의 거리를 기록하는 리스트
  처음에는 무한대로 초기화하고, 더 작은 경로를 찾을 때마다 거리 값을 갱신한다.

• 가장 가까운 정점을 꺼내올 수 있는 우선순위 큐
  BFS에서는 다음에 방문할 정점들을 큐에 넣었지만, 다익스트라에서는 지금까지 발견된 가장 가까운 거리의 정점에 대해서 먼저 계산할 수 있도록 우선순위 큐에 인접 정점들을 저장한다. 가장 가까운 정점부터 큐에서 꺼내며 미리 거리를 갱신해 놓으면, 그보다 더 먼 거리의 경로에 대해서는 더 이상 고려할 필요가 없어진다.
  
  

다익스트라 알고리즘 프로세스

1. 시작 정점 자신을 제외한 모든 정점까지의 거리를 무한대로 초기화한다.
2. 시작 정점을 우선순위 큐에 삽입한다.
3. 우선순위 큐에서 정점 하나를 꺼낸 후 해당 정점에서 갈 수 있는 모든 인접한 정점들을 확인한다.
   3-1. 인접 정점까지의 거리가 이미 기록된 해당 정점까지의 거리보다 더 짧다면 거리 값을 갱신한다.
   3-2. 이미 기록된 인접 정점까지의 거리가 더 짧다면 넘어간다.
4. 3-1에서 거리 값이 갱신된 정점들을 우선순위 큐에 삽입한다.
5. 우선순위 큐에 더 이상 정점이 없을 때까지 3~4번 과정을 반복한다.
   
   

다익스트라 알고리즘 코드 (Python)

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_node = heapq.heappop(queue)
        
	# 이미 구한 거리 배열보다 현재까지 거리가 크다면 인접 노드를 방문하는 시나리오를 고려할 필요 없음
        if distances[current_node] < current_distance:
            continue
            
        for adjacent, weight in graph[current_node].items():
	    # 현재 정점까지 온 거리 + 다음 인접한 정점까지의 거리
            distance = current_distance + weight
            
	    # 인접한 정점까지의 거리가 시작정점에서 바로 갔을 때 보다 현재 정점을 거쳤을 때 더 가깝다면 거리 갱신
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
                
    return distances


# 방향 그래프
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}
}

print(dijkstra(graph, 'A'))

※ 코드 참조 : 잔재미코딩 - 최단 경로 알고리즘의 이해

시간 복잡도

다익스트라 알고리즘은 크게 각 정점마다 인접한 간선들을 탐색하는 과정과 우선순위 큐에 [거리, 정점] 정보를 넣고 빼는 과정으로 나뉜다.

• 각 정점마다 인접한 간선들을 탐색하는 과정
  각 노드는 최대 한 번씩 방문하기 때문에 그래프의 모든 간선은 최대 한 번씩 검사한다. 따라서 이 과정의 시간 복잡도는 $O(E)$이다.

• 우선순위 큐에 [거리, 정점] 정보를 넣고 빼는 과정
  최악의 경우는 모든 간선을 검사할 때 마다 거리 값 리스트가 갱신되고, 우선순위 큐에 정보가 저장되는 경우이다. E개의 간선을 검사할 때 마다 우선순위 큐를 유지해야 하므로 이 과정의 시간 복잡도는 $O(ElogE)$이다.

위 두 과정을 거칠 경우 다익스트라 알고리즘의 총 시간 복잡도는 $O(E) + O(ElogE) = O(ElogE)$ 가 된다.