다익스트라 알고리즘

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split()) #노드 갯수, 간선 갯수
start = int(input()) #시작 노드 번호
graph = [[] for _ in range(n+1)] #노드정보 그래프
visited = [False] * (n+1) #방문 초기값은 모두 false
distance = [INF] * (n+1) #초기 거리는 모두 무한대

for i in range(m):
    a, b, c = map(int, input().split()) #a노드 -> b노드, c비용
    graph[a].append((b,c))

#방문하지 않은 노드중에서 최단거리가 짧은 노드의 번호 반환
def get_smallest_node():
    min_value = INF
    node_index = 0
    for i in range(1,n+1): #각 노드 방문
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            node_index = i
    return node_index

def dijkstra(start):
    #초기 노드 설정
    distance[start] = 0 #시작 노드의 거리는 0으로
    visited[start] = True #방문 처리
    print('distance',distance)
    for j in graph[start]: #[(a,b), (c,d)]
        #j[0]은 인접 노드 번호, j[1]은 거리
       distance[j[0]] = j[1] #인접노드의 거리를 지정해줌
       print('distance',distance)
    
    #시작노드를 제외한 전체 노드에 대해 반복
    for _ in range(n-1):
        now = get_smallest_node() #노드 인덱스 반환
        print('now', now)
        visited[now] = True #노드 방문처리
        print('visited', visited)
        for j in graph[now]: #[(a,b), (c,d)]
            #j[0]은 인접 노드 번호, j[1]은 거리
            newDistance = distance[now] + j[1] #새로운 거리는 현재노드까지의 거리 + 현재노드에서 인접노드까지의 거리
            distance[j[0]] = min(distance[j[0]], newDistance) #기존 거리와 새로운 거리중 작은걸 선택
            print('distance', distance)

print(graph)  
dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print('INFINITY')
    else:
        print(distance[i])

그래프

1 - 2,3,4 // 2 - 3,4 // 3 - 2,5 // 4 - 3,5 // 5 - 3,6

27~33번줄

• 초기노드가 1, 인접노드가 2,3,4이므로 distance[2,3,4]의 값은 거리로 할당

36~45번줄

• 시작노드에서 4번노드 까지의 거리가 가장 짧으므로 4번노드를 다음으로 방문
• 4번 노드 방문처리
• 4번 노드의 인접노드는 3,5 이므로 distance[3,5]는
  (1->4번노드 거리 + 4->3or5번노드 거리) 와 기존의 distance[3,5] 값중 작은 값을 가짐
• distance 배열에서 방문하지 않은 노드 중 가장 짧은 거리의 노드 방문 및 방문 처리
• 기존distance[now]와 새로운 newDistance중 짧은 값을 할당
• 모든 노드를 방문할 때까지 3, 4 반복
  
  
  
  

최종

최종적으로 구하고자 하는것은 1번노드에서부터 각 노드까지의 최단 거리이므로
graph배열을 반복하여 값이 INF와 같으면 INFINITY를, 아니면 해당 값을 출력