[Algorithm] 다익스트라(dijkstra) 알고리즘

최단 경로 알고리즘

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
• 하나의 시작 정점에서 끝 정점까지 최단 경로
  • 다익스트라 알고리즘 : 음의 가중치 허용x
  • 벨만-포드 알고리즘 : 음의 가중치 허용
• 모든 정점들에 대한 최단 경로
  • 플로이드 워샬 알고리즘

 

다익스트라(dijkstra) 알고리즘

• 시작 정점에서 거리가 최소인 정점을 선택해나가면서 최단 경로 구함
• 탐욕 기법 사용, MST의 프림 알고리즘과 유사

def dijkstra(start):
    distance[start] = 0

    # 노드의 개수만큼 반복
    for _ in range(N+1):
        min_idx = -1
        min_value = float('inf')

        for i in range(N+1):
            if not visited[i] and distance[i] < min_value:
                min_idx = i
                min_value = distance[i]
        
        visited[min_idx] = 1

        for i in range(N+1):
            if mat[min_idx][i] and not visited[i]:
                distance[i] = min(distance[i], distance[min_idx]+mat[min_idx][i])


T = int(input())

for t in range(1, T+1):
    N, E = map(int, input().split())
    edges = [list(map(int, input().split())) for _ in range(E)]

    # 인접 행렬
    mat = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for s, e, w in edges:
        mat[s][e] = w
    
    visited = [0 for _ in range(N+1)]
    distance = [float('inf') for _ in range(N+1)]

    dijkstra(0)

    print('#{} {}'.format(t, distance[N]))