알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 다익스트라

08-4 다익스트라

그래프에서 최단 거리를 구하는 알고리즘

- 출발 노드와 모든 노드 간의 최단 거리 탐색

- 에지는 모두 양수

 

• 다익스트라 알고리즘의 핵심이론

1. 인접 리스트로 그래프 구현하기

데이터를 자료 구조에 담는다

graph = [ [] for _ in range(n+1)]
    
for n1, n2, w in fares:
    graph[n1].append((n2, w))
    graph[n2].append((n1, w))

 

2. 최단 거리 배열 초기화하기

출발 노드 = 0, 이외의 노드는 = max 값 (충분히 큰 값)

D = [ 100001 for _ in range(n+1) ]
D[s] = 0

 

3. 값이 가장 작은 노드 고르기

처음에는 출발 노드

 

4. 최단 거리 배열 업데이트 하기

선택된 노드에 연결된 에지의 값을 보고 Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

 

5. 모든 노드가 처리될 때까지 3~4를 반복

한 번 선택된 노드는 다시 선택되지 않도록 처리 -> visited 배열

 

결과적으로 나온 배열은 시작 노드에서 모든 노드(i)까지의 최단 거리를 알 수 있음

# heapq X

def dijkstrap(n, start, graph):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    
    # 방문 여부 체크
    visited = [False] * (n + 1)
    
    for _ in range(n):
        # 방문하지 않은 노드 중 가장 짧은 거리를 가진 노드 선택
        min_dist = float('inf')
        node = -1
        for i in range(1, n + 1):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                node = i
        
        visited[node] = True
        
        # 선택된 노드와 인접한 노드들의 거리 갱신
        for next_node, weight in graph[node]:
            if dist[next_node] > dist[node] + weight:
                dist[next_node] = dist[node] + weight
    
    return dist
    
# heapq 사용
import heapq

def dijkstra(n, start, graph):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    
    # 우선순위 큐 사용
    queue = [(0, start)]  # (거리, 노드)
    
    while queue:
        current_dist, node = heapq.heappop(queue)
        
        # 이미 처리된 노드라면 무시
        if current_dist > dist[node]:
            continue
        
        # 현재 노드에서 인접한 노드들로 가는 거리 갱신
        for next_node, weight in graph[node]:
            distance = current_dist + weight
            if distance < dist[next_node]:
                dist[next_node] = distance
                heapq.heappush(queue, (distance, next_node))
    
    return dist