[알고리즘]최단 경로를 위한 다익스트라(Dijkstra) 알고리즘

그래프 관련 문제를 풀던 중 다익스트라(Dijkstra) 알고리즘을 활용한 문제를 풀게 되어 문제 풀이와 함께 알고리즘을 정리해보려 한다.

 

문제는 백준 1753번(최단경로)으로 다익스트라(Dijkstra)알고리즘 그대로 풀면 되는 문제이지만 생각보다 난이도가 있었다.

https://www.acmicpc.net/problem/1753

1753번: 최단경로

다익스트라(Dijkstra)알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.

이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 여기서 주의해야 할 점은 어느 간선의 가중치라도 음수가 있으면 안된다.

 

알고리즘의 동작 단계는 다음과 같다.

  1. 출발노드와 도착노드를 설정한다.

  2. 방문하지 않은 정점 중 가중치 값이 가장 작은 정점을 방문한다.

  3. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 구한 값보다 작다면 그 거리를 갱신한다.

  4. 2~3번 과정을 반복한다.

 

풀이

import heapq
import sys
input = sys.stdin.readline

v, e = map(int, input().split()) # 정점, 간선의 개수
k = int(input()) # 시작 정점의 번호
INF = int(1e9)
distance = [INF] * (v+1) # 최단 거리 배열
graph = [[] * (v+1) for _ in range(v+1)]

for _ in range(e):
    # u -> b, 비용 : w
    u, b, w = map(int, input().split())
    graph[u].append((b, w))

   
def dijkstra(start):
    que = []
    # que에 시작노드로 가기 위한 최단 경로를 0으로 설정하여 삽입
    # heappush(원소를 추가할 대상 리스트, 추가할 원소)
    heapq.heappush(que, (0, start))
    distance[start] = 0

    while que:
        # 최단거리가 가장 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(que) 

        # 최단거리가 아닌 경우 스킵
        if distance[now] < dist: # 해당 조건을 만족한다는 것은 최단거리를 구했다는 것!
            continue

        # 현재 노드와 인접한 다른 노드들 확인 -> 현재 노드에서 방문할 수 있는 정점들에 대한 거리 갱신    
        # graph[출발정점] : (도착정점, 가중치)
        for next_node, weight in graph[now]:
            # next_node : 현재 노드와 인접한 노드, weight : next_node까지 가는데 드는 비용
            # 현재 노드까지의 비용 + 현재노드에서 next_node까지 가는데 드는 비용
            cost = dist + weight
            
            # 이전에 구한 next_node까지의 거리보다 cost가 작으면 갱신
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(que, (cost, next_node))

dijkstra(k)

for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

 

위 코드의 다익스트라 함수의 전체적인 흐름을 다시 한 번 정리해보자.

- 시작정점을 인수로 받아 시작정점의 최단경로를 0으로 설정해 que에 push

- 시작정점의 최단 거리 배열 값을 0으로 설정

- while que

   1. 큐 내에서 최단거리를 갖는 값 pop -> 최단거리, 정점 

   2. 해당 최단거리가 최종 최단거리값인지 확인

   3. 해당 정점에서 방문할 수 있는 정점까지의 거리를 갱신하기 위한 반복문 실행

       - 해당 정점을 방문하고 다음 정점을 방문했을 때의 비용과 비교해 최단 거리 배열 값 갱신

       - 갱신했을 경우 que에 갱신한 최단거리값과 정점 push