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

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

1. 문제 정의

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

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

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

3. 알고리즘 동작 원리

1. 시작 정점의 거리를 0으로 초기화, 나머지 정점은 무한대로 설정.
2. 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택.
3. 선택한 정점을 거쳐 다른 정점으로 가는 거리가 기존 거리보다 짧으면 업데이트.
4. 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 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
1 5

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

알고리즘 진행:

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

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

6. 시간 복잡도

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

7. 결론

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

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

1. 알고리즘의 기본 원리

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

2. 상세 동작 과정

1. 초기화:
   • 시작 노드의 거리를 0으로 설정.
   • 다른 모든 노드의 거리를 무한대로 설정.
   • 방문하지 않은 노드 집합 Q를 모든 노드로 초기화.
2. 반복:
   • Q에서 거리가 최소인 노드 u를 선택.
   • u를 Q에서 제거.
   • u의 각 이웃 노드 v에 대해:
     • u를 거쳐 v로 가는 새로운 경로의 거리 계산.
     • 새 경로가 기존 경로보다 짧으면 v의 거리 업데이트.
3. 종료:
   • 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. 다익스트라 알고리즘의 한계

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

6. 실제 응용 사례

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

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[] // 계산된 거리값과 목적지를 리턴