경로 계획 알고리즘에서 경로 계산 방식에 따른 분류

1. (One-to-One) : 한 출발점에서 한 도착점까지의 최단 경로 찾기
2. (Many-to-One / One-to-Many) : 여러 출발점에서 하나의 도착점/~까지 최단 경로, 각 출발지/~에서 도착점까지 최단 경로를 찾은 뒤 그 중에서 최단 경로 선택
3. (Many-o-Many) : 여러 출발점에서 여러 도착점까지의 최단 경로

Dijkstra algorithm

단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 그래프 탐색 알고리즘(One-to-Many)으로, 네트워크가 가중 그래프로 표현된다. 이 때 음수 가중치는 존재하지 않으며 도로 네트워크, 통신 네트워크 등에서 주로 활용된다.

동작 과정

# 전체적 동작 과정에 대한 pseudo code

다익스트라(그래프 G, 시작 노드 s):
    # 거리 테이블 초기화 : 출발 노드까지의 거리를 무한대로 설정하고, 시작 노드의 거리는 0으로 설정
    거리테이블 = {노드: 무한대, ...}
    거리테이블[s] = 0
    
    # 방문한 노드를 추적하는 집합
    방문한노드 = 빈 집합
    
    # 아직 처리되지 않은 모든 노드를 포함하는 우선순위 큐
    우선순위큐 = 우선순위 큐()
    우선순위큐.삽입((s, 0))  # 시작 노드
    
    # 우선순위 큐가 비어있을 때까지 반복
    while 우선순위큐가 비어있지 않을 때까지:
        # 현재까지 방문한 노드 중에서 거리가 가장 짧은 노드 선택
        현재노드, 현재거리 = 우선순위큐.최소거리노드_반환()
        우선순위큐.삭제(현재노드)
        
        # 방문한 노드에 현재 노드 추가
        방문한노드.추가(현재노드)
        
        # 현재 노드와 연결된 모든 이웃 노드에 대해 최단 경로 갱신
        for 이웃노드 in 현재노드의_이웃노드:
            # 출발 노드를 거쳐서 이웃 노드로 가는 거리 계산
            새거리 = 현재거리 + 현재노드에서_이웃노드까지_가는_거리
            
            # 현재까지의 최단 거리보다 새로운 거리가 더 짧으면 업데이트
            if 새거리 < 거리테이블[이웃노드]:
                거리테이블[이웃노드] = 새거리
                우선순위큐.삽입((이웃노드, 새거리))
    
    return 거리테이블

1. 시작 노드 설정 : 시작 노드를 선택하고 해당 노드로부터 갈 수 있는 모든 노드까지의 최단 경로 찾기
2. 거리 테이블 초기화 : 시작 노드를 제외한 모든 노드의 거리를 무한대 INF로 설정(시작 노드 거리는 0)
3. 우선순위 큐 : 우선순위 큐를 사용해 다음 방문할 노드를 선택(초기에는 시작 노드만 우선순위 큐에 존재)
4. 반복 수행
   ① 우선순위 큐에서 거리가 가장 짧은 노드 선택(MinHeap 사용)
   ② 선택된 노드 방문해서 해당 노드로부터 갈 수 있는 모든 노드에 대해 현재 거리 테이블의 최단 거리보다 더 짧은 경로가 있다면 짧은 경로로 업데이트하고 우선순위 큐에 추가
5. 종료 : 위 반복을 우선순위 큐가 빌 때까지 반복하며 모든 노드에 대한 최단 경로가 결정되면 종료

코드 구현

import heapq

def dijkstra(graph, start):
    # 거리 테이블 초기화 : 시작 노드부터의 거리를 무한대로 설정
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # 우선순위 큐 준비: (거리, 노드) 형태로 저장
    pq = [(0, start)]
    
    while pq:
        # 우선순위 큐에서 가장 짧은 거리의 노드 선택
        current_distance, current_node = heapq.heappop(pq)
        
        # 이미 처리된 노드인 경우 건너뜀
        if current_distance > distances[current_node]:
            continue
        
        # 현재 노드와 연결된 모든 이웃 노드에 대해 최단 거리 갱신
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # 현재까지의 최단 거리보다 새로운 거리가 더 짧으면 업데이트
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

if __name__=="__main__":
    # 그래프 예시 (인접 리스트로 표현)
    graph = {
        'A': {'B': 5, 'C': 3},
        'B': {'A': 5, 'C': 2, 'D': 1},
        'C': {'A': 3, 'B': 2, 'D': 4, 'E': 6},
        'D': {'B': 1, 'C': 4, 'E': 2},
        'E': {'C': 6, 'D': 2}
    }

    start_node = 'A'
    distances = dijkstra(graph, start_node)
    print("최단 거리:", distances)

그래프 정보를 딕셔너리 형태의 인접 리스트로 전달하며 딕셔너리의 키는 이웃 노드, 값은 가중치로 가정한다. heapq로 우선순위 큐를 사용하였다.

정리

다익스트라 알고리즘에서 거리 테이블은 최단 경로가 갱신될 때마다 출발 노드에서 해당 노드까지의 경로가 짧아지는 방향으로만 업데이트된다. 이러한 방식으로 더이상 업데이트되지 않을 때까지 최적의 경로를 탐색한다.
다익스트라 알고리즘은 그리디 알고리즘으로, 탐색 과정에서 한 노드에서 다른 노드로의 경로를 탐색하며 점진적으로 탐색 깊이를 증가시킨다는 점에서 BFS와 유사하다. 하지만 BFS는 unweighted 그래프에서의 탐색이라는 점에서 차이를 갖는다.

• 출발 노드로부터 다른 모든 노드 간 최단 경로를 찾기에 정확한 최단 경로를 찾을 수 있다는 장점
• 시간 복잡도는 O((V+E)logV)로, 노드와 간선의 수에 비례하여 계산 비용이 증가한다. 따라서 그래프가 매우 크거나 밀집되어 있을 경우에는 계산 시간 길어질 수도
• 그래프 구조가 동적으로 변경되는 경우, 대처 어려움