[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점(출발점)으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 

• 필수 조건 : 모든 간선의 가중치는 0 이상의 값이어야 하며, 음수 가중치가 존재하면 올바른 결과를 보장할 수 없습니다. → 음수 가중치는 나중에 배울 벨만-포드 알고리즘을 사용합니다.
• 분류: 그리디 접근 방식으로 매 단계마다 "현재까지의 최단 경로"를 이용하여 다음 정점을 선택합니다.

---

동작 과정 및 의사 코드

1. 초기화

• 모든 노드까지의 최단 거리를 무한대(INF)로 설정 → 최단 거리기 때문에 초기 값을 무한대로 설정
• 시작 노드의 최단 거리는 0으로 설정
• 우선순위 큐(힙)에 (거리, 노드) 형태로 시작 노드를 추가 → (거리, 노드) / (노드, 거리) 상관 X 단) 거리 기준으로 우선순위를 부여

2. 우선순위 큐(힙)에서 노드 탐색

• 큐가 빌때까지 반복
• 현재 최단 거리로 도달 가능한 노드를 큐에서 꺼냄
• 이미 더 짧은 경로가 존재하는 경우를 무시

3. 현재 노드와 연결된 모든 인접노드 탐색

• 인접한 노드들 하나씩 확인
• 현재 노드를 거쳐 가는 새로운 거리(비용)를 계산
• 만약 새로운 거리가 기준보다 짧다면 갱신
• 갱신된 노드를 우선순위 큐에 추가

4. 모든 노드를 처리하면 종료

• 최단 거리를 담은 리스트에 모든 노드의 최소 비용이 저장됨

의사 코드

import heapq

def dijkstra(n, start, graph):
    """
    다익스트라 알고리즘을 통해 시작 노드로부터 다른 모든 노드까지의 최단 경로를 구하는 함수.
    
    매개변수:
        n (int): 노드의 총 개수 (노드 번호는 1부터 n까지)
        start (int): 시작 노드 번호
        graph (list): 인접 리스트 형태의 그래프. 각 인덱스 i는 (노드, 가중치) 튜플 리스트를 포함.
        
    반환값:
        distance (list): 시작 노드로부터 각 노드까지의 최소 비용 리스트.
    """
    
    INF = int(1e9)  # 무한대를 의미하는 값 (여기서는 10억 사용)
    # 최단 거리 테이블을 무한대로 초기화 (1번부터 n번 노드까지)
    distance = [INF] * (n + 1)
    distance[start] = 0  # 시작 노드까지의 거리는 0으로 설정
    
    # 우선순위 큐(최소 힙) 초기화 및 시작 노드 추가
    q = []
    heapq.heappush(q, (0, start))  # (현재까지의 비용, 노드)
    
    # 큐가 빌 때까지 반복하면서 최단 경로 탐색
    while q:
        # 가장 비용이 적은 노드 (currentDistance, currentNode)를 큐에서 꺼냄
        dist, now = heapq.heappop(q)
        
        # 이미 더 짧은 경로가 기록되어 있다면 무시
        if dist > distance[now]:
            continue
        
        # 현재 노드(now)에 연결된 모든 인접 노드(i) 탐색
        for i in graph[now]:
            # i[0]: 인접 노드, i[1]: 현재 노드에서 인접 노드로 가는 비용
            cost = dist + i[1]  # 현재 노드를 거쳐 인접 노드로 가는 새로운 비용 계산
            
            # 만약 새로운 비용이 기존의 최단 경로보다 짧다면
            if cost < distance[i[0]]:
                # 최단 거리 갱신
                distance[i[0]] = cost
                # 갱신된 인접 노드를 우선순위 큐에 추가하여 이후에 처리
                heapq.heappush(q, (cost, i[0]))
                
    return distance

# 예시 사용법:
if __name__ == "__main__":
    # 노드 수와 간선 수를 정의 (예시: 5개의 노드)
    n = 5  
    start = 1  # 시작 노드 설정
    # 그래프 초기화 (1번부터 5번 노드까지)
    graph = [[] for _ in range(n + 1)]
    
    # 예시: 간선 추가 (a, b, c: a 노드에서 b 노드로 가는 비용 c)
    # 아래는 임의의 간선 예시입니다.
    graph[1].append((2, 2))
    graph[1].append((3, 5))
    graph[2].append((3, 1))
    graph[2].append((4, 2))
    graph[3].append((4, 3))
    graph[4].append((5, 1))
    
    # 다익스트라 알고리즘 실행
    shortest_distances = dijkstra(n, start, graph)
    
    # 결과 출력: 각 노드까지의 최단 거리
    for i in range(1, n + 1):
        print(f"노드 {start}에서 노드 {i}까지의 최단 거리: {shortest_distances[i]}")

---

장단점

장점

• 구현이 간단 → 아직 미숙해서 어렵나 봐요....
  개념이 직관적이며, 기본적인 자료구조(배열, 우선순위 큐 등)만 있으면 쉽게(?????) 구현할 수 있습니다. 
• 정확한 최단 경로 산출
  음수 가중치가 없는 그래프에서 항상 정확한 최단 경로를 보장합니다. 
• 실제 경로 추적 가능
  최단 거리뿐만 아니라, 경유한 노드들을 기록하여 실제 경로를 재구성할 수 있습니다. 

단점

• 음수 가중치에 취약
  그래프의 음의 가중치가 존재할 경우 올바른 결과를 보장하지 않습니다. 
• 대규모 그래프의 경우 성능 문제
  정점(Vertex)과 간선(Edge)의 수가 매우 많을 경우, 우선순위 큐 사용 시에도 계산 비용이 증가할 수 있습니다. 
• 동적 그래프에 부적합
  노드나 간선이 자주 변경되는 환경에서는 매번 저체 알고리즘을 재실행해야 하므로 비효율적입니다. 

---

실생활에서의 다익스트라

1. GPS 내비게이션 시스템

• 설명: 차량의 출발지에서 목적지까지 최적의 경로를 찾기 위해 사용됩니다.
• 실제 활용: 지도상의 도로 거리와 교통 상황 등을 반영하여 운전자에게 빠르고 효율적인 경로를 안내합니다.

2. 네트워크 라우팅

• 설명: 데이터 패킷이 네트워크를 통해 최종 목적지에 도달하는 최적의 경로를 결정합니다.
• 실제 활용: OSPF(Open Shortest Path First)와 같은 라우팅 프로토콜은 네트워크 상의 노드들 간 최단 경로를 산출하여 데이터 전송 효율을 극대화합니다.

3. 물류 및 배송 최적화

• 설명: 여러 창고나 배송지 간의 이동 경로를 최적화하여 비용과 시간을 절감합니다.
• 실제 활용: 배송 경로를 최적화함으로써 연료 비용을 줄이고, 배송 시간을 단축하는 데 기여합니다.