다익스트라 알고리즘: 최단 경로 찾기

1. 문제 정의

문제는 N개의 도시와 M개의 버스 노선이 주어졌을 때, 특정 출발 도시에서 도착 도시까지의 최소 비용을 찾는 것. 각 버스 노선은 출발 도시, 도착 도시, 비용으로 구성.

2. 다익스트라 알고리즘 개요

다익스트라 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘. 음의 가중치가 없는 그래프에서 사용 가능.

3. 알고리즘 동작 원리

시작 정점의 거리를 0으로 초기화, 나머지 정점은 무한대로 설정.
방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택.
선택한 정점을 거쳐 다른 정점으로 가는 거리가 기존 거리보다 짧으면 업데이트.
2-3 과정을 모든 정점을 방문할 때까지 반복.

4. 코드 분석

4.1 입력 및 그래프 초기화

N, M, *bus = map(int, open(0).read().split())
graph = [[float('inf') for * in range(N+1)] for * in range(N+1)]
for i in range(0, M*3, 3):
    graph[bus[i]][bus[i+1]] = min(graph[bus[i]][bus[i+1]], bus[i+2])
A, B = bus[-2], bus[-1]

N: 도시의 수, M: 버스 노선의 수.
graph: 2차원 리스트로 그래프 표현. 초기값은 무한대.
버스 정보를 이용해 graph 업데이트.
A: 출발 도시, B: 도착 도시.

4.2 다익스트라 알고리즘 구현

distances = [float('inf')] * (N+1)
distances[A] = 0
queue = [(0, A)]
while queue:
    current_distance, current_node = heapq.heappop(queue)
    if current_distance > distances[current_node]:
        continue
    if current_node == B:
        break
    for next_node, next_distance in enumerate(graph[current_node]):
        distance = current_distance + next_distance
        if distance < distances[next_node]:
            distances[next_node] = distance
            heapq.heappush(queue, (distance, next_node))

distances: 각 도시까지의 최단 거리 저장.
queue: 우선순위 큐로 구현, 거리가 짧은 노드부터 처리.
while 루프: 큐가 빌 때까지 반복.
현재 노드에서 이동 가능한 모든 노드 확인.
더 짧은 경로 발견 시 distances 업데이트 및 큐에 추가.

5. 예시 데이터로 알고리즘 이해하기

예시 입력:

5개의 도시, 7개의 버스 노선.
출발 도시: 1, 도착 도시: 5.

알고리즘 진행:

초기 상태: distances = [inf, 0, inf, inf, inf, inf]
노드 1 처리: distances = [inf, 0, 2, 3, 1, 10]
노드 4 처리: distances = [inf, 0, 2, 3, 1, 10] (변화 없음)
노드 2 처리: distances = [inf, 0, 2, 3, 1, 10] (변화 없음)
노드 3 처리: distances = [inf, 0, 2, 3, 1, 4]

최종 결과: 1번 도시에서 5번 도시까지의 최소 비용은 4.

6. 시간 복잡도

우선순위 큐 사용 시: O((V+E)logV), V는 정점 수, E는 간선 수.
이 구현에서는 heapq 모듈 사용으로 효율적인 우선순위 큐 구현.

7. 결론

다익스트라 알고리즘은 효율적으로 최단 경로를 찾는 알고리즘. 우선순위 큐를 사용하여 최적화 가능. 다양한 경로 찾기 문제에 적용 가능한 강력한 도구.

다익스트라 알고리즘: 심화 이해

1. 알고리즘의 기본 원리

다익스트라 알고리즘의 핵심 아이디어는 ‘그리디(greedy)’ 선택. 매 단계에서 가장 비용이 적은 노드를 선택하여 최단 경로를 확장.

2. 상세 동작 과정

초기화:
- 시작 노드의 거리를 0으로 설정.
- 다른 모든 노드의 거리를 무한대로 설정.
- 방문하지 않은 노드 집합 Q를 모든 노드로 초기화.
반복:
- Q에서 거리가 최소인 노드 u를 선택.
- u를 Q에서 제거.
- u의 각 이웃 노드 v에 대해:
  - u를 거쳐 v로 가는 새로운 경로의 거리 계산.
  - 새 경로가 기존 경로보다 짧으면 v의 거리 업데이트.
종료:
- Q가 비어있거나 도착 노드에 도달하면 종료.

3. 구현 최적화

3.1 우선순위 큐 사용

import heapq

def dijkstra(graph, start, end):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if current_distance > distances[current_node]:
            continue
        
        if current_node == end:
            return current_distance
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    
    return float('inf')

heapq 모듈 사용으로 O(log N) 시간에 최소 거리 노드 선택 가능.
전체 시간 복잡도: O((V + E) log V), V는 정점 수, E는 간선 수.

3.2 인접 리스트 사용

그래프 표현에 2차원 리스트 대신 딕셔너리 사용:

graph = {
    1: {2: 2, 3: 3, 4: 1, 5: 10},
    2: {4: 2},
    3: {4: 1, 5: 1},
    4: {},
    5: {}
}

메모리 사용 효율성 증가.
노드 탐색 시간 감소.

4. 다익스트라 vs 다른 최단 경로 알고리즘

4.1 벨만-포드 알고리즘

음의 가중치 처리 가능.
시간 복잡도 O(VE)로 다익스트라보다 느림.

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

모든 노드 쌍 간의 최단 경로 계산.
시간 복잡도 O(V^3).
작은 그래프에 적합.

5. 다익스트라 알고리즘의 한계

음의 가중치 처리 불가:
- 음의 가중치가 있으면 무한 루프 발생 가능.
대규모 그래프에서의 성능:
- 노드 수가 매우 많은 경우 여전히 느릴 수 있음.

6. 실제 응용 사례

네비게이션 시스템:
- 실시간 교통 정보를 가중치로 사용.
네트워크 라우팅:
- 데이터 패킷의 최적 경로 결정.
물류 시스템:
- 최적의 배송 경로 계산.

7. 발전된 형태의 다익스트라 알고리즘

7.1 양방향 검색 (Bidirectional Search)

시작점과 끝점에서 동시에 검색 시작.
두 검색이 만나는 지점에서 최단 경로 형성.

7.2 A* 알고리즘

휴리스틱 함수를 사용하여 검색 방향 가이드.
다익스트라의 확장 버전으로, 특정 상황에서 더 효율적.

8. 결론

다익스트라 알고리즘은 효율적이고 다재다능한 최단 경로 알고리즘. 다양한 최적화 기법과 변형을 통해 실제 문제에 폭넓게 적용 가능. 그러나 특정 제한사항을 인지하고 상황에 맞는 알고리즘 선택이 중요.

import heapq

# 입력 받기
N, M, *bus = map(int, open(0).read().split())

# 그래프 초기화
graph = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
for i in range(0, M*3, 3):
    graph[bus[i]][bus[i+1]] = min(graph[bus[i]][bus[i+1]], bus[i+2])

# 출발 도시와 도착 도시 입력 받기
A, B = bus[-2], bus[-1]

# 다익스트라 알고리즘 구현
distances = [float('inf')] * (N+1)
distances[A] = 0
queue = [(0, A)]

while queue:
    current_distance, current_node = heapq.heappop(queue)

    if current_distance > distances[current_node]:
        continue

    if current_node == B:
        break

    for next_node, next_distance in enumerate(graph[current_node]):
        distance = current_distance + next_distance
        if distance < distances[next_node]:
            distances[next_node] = distance
            heapq.heappush(queue, (distance, next_node))

# 결과 출력
result = distances[B]
print(result if result != float('inf') else -1)

https://youtu.be/tZu4x5825LI

의사코드(출처 나무위키)

Graph는 모든 노드와 노드 간의 거리, 이웃노드에 관한 정보를 포함한다.
Source는 출발할 노드를 의미한다.

prev[(node)]는 출발지까지 가장 빠르게 갈 수 있다고 계산된 이웃 노드를 가리킨다. 즉, 출발지부터 목적지까지의 경로가 아니라, 목적지부터 출발지까지의 경로를 기록한다.
dist[(node)]는 출발지부터 현재 node까지의 cost 값을 의미한다.

function Dijkstra(Graph, Source):
 dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
 prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined
 create vertex set Q // 노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작
 for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화
 if v ≠ source: // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)
 dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 (모든 노드들을 초기화하는 값)
 prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화
 add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가
//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
 while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로!
 u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
 remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거
 for each neighbor v of u: // U의 이웃노드들과의 거리 측정
 alt ← dist[u] + length(u, v) // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
 // = source to U + V to U = source to U
 if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
 dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
 prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈
 return dist[], prev[] // 계산된 거리값과 목적지를 리턴

저작자표시 비영리 변경금지

붉은 각설탕

백준1916🐨최소비용 구하기.py(다익스트라 알고리즘: 최단 경로 찾기)