다익스트라 알고리즘

import heapq

def solution(graph, start):

# 1. 시작 노드 설정, 시작 노드부터 특정 노드까지 최소 비용을 저장할 공간과 직전 노드를 저장할 공간 마련
# 1-1. 최소 비용을 저장할 공간은 모두 매우 큰 값으로 초기화
# 무한대 약자는 INF 로 표현, 직전 노드를 저장할 공간 또한 INF로 초기화 
# 1-2. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로

# 2. 해당 노드를 ㅌ오해 방문할 수 있는 노드 중, 아직 방문하자ㅣ 않는 노드 중 현재까지 구한 최소 비용이 
# 가장 작은 노드를 선택
# 2-1. 해당 노드를 거쳐 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교해 작은 값을
# 각 노드의 최소 비용으로 갱신함
# 2-2. 이때 직전 노드도 같이 갱신함.
# 3. 노드 개수에서 1을 뺀 만큼 반복함.
    
    distances = {node: float("inf") for node in graph}
    # 1. 모든 노드의 거리 값을 무한대로 초기화 
    # print(distances)

    distances[start] = 0 
    # 2. 시작 노드의 거리 값은 0으로 초기화 

    queue = []
    heapq.heappush(queue, [distances[start], start]) 
    # print('queue', queue) # [[0, 'A']]

    # 3. 시작 노드를 큐에 삽입
    paths = {start: [start]} # paths:  {'A': ['A']} 이렇게 나오는게 맞나,,? 
    # 4. 시작 노드의 경로를 초기화 

    # print('paths: ', paths)

    while queue:
        # 5. 현재 가장 거리 값이 작은 노드를 가져옴
        current_distance, current_node = heapq.heappop(queue)
        # 6. 만약 현재 노드의 거리 값이 큐에서 가져온 거리 값보다 크면,
        # 해당 노드는 이미 처리한 것이므로 무시

        if distances[current_node] < current_distance:
            continue

        # 7. 현재 노드와 인접한 노드들의 거리 값을 계산하여 업데이트
        
        for adjacent_node, weight in graph[current_node].items():
            distance = current_distance + weight
            # 8. 현재 계산한 거리 값이 기존 거리 값보다 작으면 최소 비용 및
            # 최단 경로 업데이트 
             
            if distance < distances[adjacent_node]:
                distances[adjacent_node] = distance # 최소 비용 업데이트
                paths[adjacent_node] = paths[current_node] + [adjacent_node]
                # 최단 경로 업데이트

                # 9. 최소 경로가 갱신된 노드를 비용과 함께 큐에 푸시
                heapq.heappush(queue, [distance, adjacent_node])

    # 10. paths 딕셔너리를 노드 번호에 따라 오름차순 정렬하여 반환
    sorted_paths = {node: paths[node] for node in sorted(paths)}

    return [distances, sorted_paths]

 

 

주석 없는 버전 

 

import heapq
def solution(graph, start):

    distances = {node: float("inf") for node in graph}
    distances[start] = 0

    queue = []
    heapq.heappush(queue, [distances[start], start])
    paths = {start: [start]}

    while queue:
        currDis, currNode = heapq.heappop(queue)

        if distances[currNode] < currDis:
            continue 

        for injeop, weight in graph[currNode].items():
            distance = currDis + weight
            if distances[currNode] > distance:
                distances[currNode] = distance
                paths[injeop] = paths[currNode] + [injeop]
                heapq.heappush(queue, [distance, injeop])

        
        sorted_paths = {node: paths[node] for node in sorted(paths)}


            
   
    return [distances, sorted_paths]