[알고리즘] 최단 경로 알고리즘 이해

1. 최단 경로 문제란?

• 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임
• 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제
   • 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 출발 (single-source shortest path problem) 최단 경로 문제
   • 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제

     따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 예를 들어 A, B, C, D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면,
     A 외 모든 노드인 B, C, D 각 노드와 A 간에 (즉, A - B, A - C, A - D) 각각 가장 짧은 경로를 찾는 문제를 의미함

3. 전체 쌍(all-pair) 최단 경로: 그래프 내의 모든 노드 쌍 (u, v) 에 대한 최단 경로를 찾는 문제

2. 최단 경로 알고리즘 - 다익스트라 알고리즘

• 다익스트라 알고리즘은 위의 최단 경로 문제 종류 중, 2번에 해당
  - 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제

다익스트라 알고리즘 로직

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
• 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사
  - 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트

  다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식에 집중해서 설명하기로 함

우선순위 큐를 활용한 다익스트라 알고리즘

• 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨

1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
   • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함 (inf 라고 표현함)
   • 우선순위 큐에 (첫 정점, 거리 0) 만 먼저 넣음
2. 우선순위 큐에서 노드를 꺼냄
   • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐
   • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교한다.
   • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
   • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
     - 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
     - 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
3. 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

구현: 탐색할 그래프의 시작 정점과 다른 정점들간의 최단 거리 구하기

1. 우선순위 큐(queue)에서 하나를 뽑는다. (heapq.pop(queue))
2. 1번에서 뽑은 노드와 인접 노드들과의 거리로 distances 리스트의 원소를 업데이트 한다. (업데이트 가능한 경우만!)
3. 2번에서 업데이트 된 원소들만 우선순위 큐에 푸시한다. (heapq.push(queue, [dist, adjacent]))

import heapq

def dijkstra(graph, start):
    
    # 초기화
    distances = {x: float('inf') for x in graph} # 각 노드까지의 거리를 inf 로 초기화
    distances[start] = 0
    queue = [] # 우선순위 큐
    heapq.heappush(queue, [distances[start], start]) # [거리, 노드] 형태로 푸시
    
    # 각 노드까지 최단 거리 계산
    while queue:
        # 우선순위 큐에서 뽑은 [거리, 노드] 를 curDistance, curNode 에 대입
        curDistance, curNode = heapq.heappop(queue)
        
        # 우선순위 큐에서 뽑은 curDistance 가 더 크다면, continue
        if distances[curNode] < curDistance:
            continue
            
        # curNode 의 [인접노드, 무게] 를 쌍으로 추출
        for adjacent, weight in graph[curNode].items():
            dist = curDistance + weight
            if dist < distances[adjacent]:
                distances[adjacent] = dist # 최단 거리 업데이트
                heapq.heappush(queue, [dist, adjacent]) # 우선순위 큐에 푸시
    
    return distances

print(dijkstra(mygraph, 'A')) # {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

활용: 다익스트라 알고리즘을 활용해 최단 경로 출력하기

import heapq

def shortestPath(graph, start, end):
    distances = {x: [float('inf'), start] for x in graph}
    distances[start] = [0, start] # [거리, 노드]
    queue = []
    heapq.heappush(queue, [distances[start][0], start])

    while queue:
        curDistance, curNode = heapq.heappop(queue)
        if distances[curNode][0] < curDistance:
            continue
            
        for adjacent, weight in graph[curNode].items():
            distance = curDistance + weight
            if distance < distances[adjacent][0]:
                distances[adjacent] = [distance, curNode]
                heapq.heappush(queue, [distance, adjacent])
    
    path = end
    path_output = end + '->'
    
    while distances[path][1] != start:
        path_output += distances[path][1] + '->'
        path = distances[path][1]
    path_output += start
    print (path_output)
    
    return distances

print(shortestPath(mygraph, 'A', 'F'))

# 출력
# F->E->D->A
# {'A': [0, 'A'], 'B': [6, 'C'], 'C': [1, 'A'], 'D': [2, 'A'], 'E': [5, 'D'], 'F': [6, 'E']}

3. 시간 복잡도

• 위 다익스트라 알고리즘은 크게 다음 두 가지 과정을 거침
  • 과정1: 각 노드마다 인접한 간선들을 모두 검사하는 과정
  • 과정2: 우선순위 큐에 노드/거리 정보를 넣고 삭제(pop)하는 과정
• 각 과정별 시간 복잡도
  • 과정1: 각 노드는 최대 한 번씩 방문하므로 (첫 노드와 해당 노드간의 갈 수 있는 루트가 있는 경우만 해당), 그래프의 모든 간선은 최대 한 번씩 검사
    • 즉, 각 노드마다 인접한 간선들을 모두 검사하는 과정은 $O(E)$ 시간이 걸림, E 는 간선(edge)의 약자
  • 과정2: 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 경우, 우선순위 큐에 노드/거리 정보를 넣고, 삭제하는 과정이 최악의 시간이 걸림
    • 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다, 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는 것임
    • 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로, 최대 $O(E)$ 의 시간이 걸리고, $O(E)$ 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 $𝑂(𝑙𝑜𝑔𝐸)$ 가 걸림
      • 따라서 해당 과정의 시간 복잡도는 $𝑂(𝐸𝑙𝑜𝑔𝐸)$
• 총 시간 복잡도
  • 과정1 + 과정2 = $O(E)$ + $𝑂(𝐸𝑙𝑜𝑔𝐸)$ = $𝑂(𝐸+𝐸𝑙𝑜𝑔𝐸)$ = $𝑂(𝐸𝑙𝑜𝑔𝐸)$

참고: 힙의 시간 복잡도

• depth (트리의 높이) 를 h라고 표기한다면,
• n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 h=$log2n$ 에 가까우므로, 시간 복잡도는 $O(logn)$

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기