[Algorithm] Shortest Path Problem

in Computer Science on Algorithm


Shortest Path Problem 최단 경로 문제

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

최단 경로 문제 종류

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


출처 : https://shnoh.tistory.com/15
상황에 따라 사용해야 할 최단 경로 문제 알고리즘


Dijkstra Algorithm 다익스트라 알고리즘

  • 하나의 노드에서 다른 모든 노드 간의 각각 가장 짧은 거리를 구하는 단일 출발 최단 경로 문제에 적합
  • 첫 노드을 기준으로 연결되어 있는 노드들을 추가해 가며, 최단 거리를 갱신하는 기법으로 BFS와 유사


다익스트라 알고리즘 로직

  • 다익스트라 알고리즘의 다양한 변형 로직이 있지만, 본 포스팅에서는 가장 개선된 우선순위 큐를 사용하는 방식을 사용
    • 우선순위 큐는 최소 힙 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼냄
  1. 첫 노드를 기준으로 배열을 선언하여 첫 노드에서 각 노드까지의 거리를 저장
    • 시간을 단축시키기 위해 접근이 빠른 해시테이블의 성질을 띄는 딕셔너리로 선언
    • 초기에는 첫 노드의 거리는 0, 나머지는 무한대(inf)로 저장
    • 우선순위 큐에 (첫 노드, 거리 0)만 먼저 넣음
  2. 우선순위 큐에서 노드를 꺼냄
    • 처음에는 첫 노드만 저장되어 있으므로, 첫 노드가 꺼내짐
    • 첫 노드에 인접한 노드들 각각에 대해, 첫 노드에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 노드에서 각 노드까지의 거리를 비교
    • 배열에 저장되어 있는 거리보다, 첫 노드에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리로 업데이트
    • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 삽입
    • 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 노드에 인접한 노드들을 순차적으로 방문
    • 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
  3. 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복


출처 : https://shnoh.tistory.com/15
우선순위 큐 방식의 다익스트라 알고리즘 로직


다익스트라 알고리즘 구현


출처 : https://www.fun-coding.org/Chapter20-shortest-live.html
다익스트라 알고리즘 구현을 위한 그래프 예시 


import heapq

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}
}

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
우선순위 큐 방식의 다익스트라 알고리즘을 파이썬으로 구현


다익스트라 알고리즘 시간 복잡도

  • 노드 수 : V / 간선 수 : E

과정 1 (각 노드마다 인접한 간선들을 모두 검사)

  • 각 노드는 최대 한 번씩 방문하므로 (첫 노드와 해당 노드간의 갈 수 있는 루트가 있는 경우만 해당), 그래프의 모든 간선은 최대 한 번씩 검사
  • 각 노드마다 인접한 간선들을 모두 검사하는 과정은 O(E) 시간이 걸림

과정 2 (우선순위 큐에 노드/거리 정보를 넣고 삭제 하는 과정)

  • 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 경우, 우선순위 큐에 노드/거리 정보를 넣고, 삭제하는 과정이 최악의 시간이 걸림

  • 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다, 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는 것
  • 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로, 최대 O(E)의 시간이 걸리고, O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 O(logE)가 걸림
  • 직관적으로 전체 과정은 O(E + ElogE) -> E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사
  • 대개의 중복 간선이 없는 경우, 그래프에서 간선의 개수 E는 V^2보다 작기 때문에 O(logE)=O(logV)
    • 따라서 우선순위 큐를 활용한 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)로 표기 가능
  • 간선이 V^2보다 한참 적은 희소 그래프가 아닌 노드의 수가 적거나 간선의 수가 매우 많은 밀집 그래프일 경우에는 아예 우선순위 큐를 사용하지 않고 구현하는 방식이 더욱 빠른 경우가 있음
  • 다음에 방문 할 노드를 매번 반복문을 이용해 방문하지 않은 노드 중 거리가 가장 작은 값을 찾아 각 노드를 방문했는지 여부를 우선 순위 큐가 아닌 일반적인 연결 리스트나 배열로 저장
    • 이 경우 다익스트라 알고리즘의 시간 복잡도는 O(V^2+E) -> O(V^2)로 표기 가능


Bellman-Ford algorithm 벨만-포드 알고리즘

  • 모든 경우의 수를 다 탐색해 가면서 최단 거리를 찾는 방식
  • 지금 당장 눈앞에 보이는, 연결되어 있는 노드들 중에서 최단 거리로 연결된 노드를 선택하는 다익스트라 방식과는 다르게 그리디하지 않게 접근
  • 다익스트라 알고리즘과는 달리 음수의 가중치가 있어도 계산이 가능하지만 시간복잡도가 높아 가중치가 모두 양일 경우에는 굳이 사용하지 않음

밸만-포드 알고리즘 로직

  1. 모든 간선들을 탐색하면서, 간선이 잇는 출발 노드가 ‘한번이라도 계산 된 노드’ 이라면 해당 간선이 잇는 노드의 거리를 비교해서 업데이트
  2. 모든 노드에서 1번 과정을 반복

벨만-포드 알고리즘 시간복잡도

  • 벨만-포드 알고리즘은 그래프 모든 간선에 대해 시작노드를 제외한 전체 노드수 만큼 반복 수행하므로, 그 시간복잡도는 O(VE)
  • 일반적으로 밀집 그래프는 간선 수가 대개 노드 수의 제곱에 근사하므로 간단하게 표현하면 O(V^3)

    이는 연결 리스트를 사용한 다익스트라 알고리즘의 시간복잡도인 O(V^2)보다 더 큼


Floyd-Warshall Algorithm 플로이드-워셜 알고리즘

  • 하나의 노드에서 다른 모든 노드로의 최단 거리를 찾는 다익스트라 알고리즘이나 벨만-포드 알고리즘과는 다르게 모든 정점에서 모든 노드로의 최단거리를 찾을 수 있는 알고리즘 (전체 쌍 최단 경로 문제)
  • 벨만-포드 알고리즘과 마찬가지로 음의 가중치도 계산 가능
  • 모든 노드에서 모든 노드를 방문해야하므로 그래프는 2차원 배열로 구성하여 해결

플로이드-워셜 알고리즘 로직

  1. 그래프의 노드와 간선에 따라 최단 거리 테이블 2차원 배열로 갱신
  2. 1번, 2번, 3번, … 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신
  3. 모든 노드를 고려하여 갱신할 때까지 2번 과정을 반복

플로이드-워셜 알고리즘 시간복잡도

  • 일반적으로 플로이드-워셜 알고리즘은 3중 반복문으로 이루어 져 있어서 세제곱 시간 알고리즘을 적용해도 될 만큼 그래프의 크기가 작을 때만 사용하는 것이 좋음
  • 시간 복잡도는 일반적인 3중 반복문의 복잡도인 O(V^3)


참고

잔재미코딩
신찬수 교수님 유튜브
위키 백과
shnoh’s Blog



© 2021. by hminkim