다익스트라

최단경로 탐색

다익스트라 알고리즘이란 그래프 이론에서 한 노드에서 다른 모든 노드로의 최단 경로를 찾는 기본적인 알고리즘이다. 음의 가중치를 갖는 경로가 있는 경우에는 플로이드-워셜 알고리즘과 벨만-포드 알고리즘이 대안으로 사용된다.

다익스트라

하나의 정점에서 다른 모든 정점으로의 최단경로를 찾는 알고리즘이다. 그래프의 간선에 음의 가중치가 있다면 사용할 수 없기 때문에 이에 유의하여 사용해야 한다.

처리 과정

1. 모든 노드들까지의 최단경로를 표현하는 테이블을 만든 후, 모든 노드로의 거리를 무한대로 설정한다. 자기 자신으로의 거리는 0으로 설정한다.
2. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드들을 관리하여 이 중 가장 가까운 노드를 선택한 후 방문 처리한다.
3. 해당 노드를 거쳐서 다른 노드로 넘어가는 비용을 고려하여 최단경로 테이블을 갱신한다.
4. 모든 노드를 방문할 때까지 2번과 3번을 반복한다.

수도코드

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

수도코드를 분석해보겠다.

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

해당 부분은 거리 테이블로, 시작점으로부터 다른 노드들로의 거리이다. 처음에는 초기화를 무한대로 해주고, 자기 자신으로만 0으로 설정한다.

    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

다익스트라는 우선순위 큐를 사용한다. 정확하게 말하자면 가장 가까운 거리부터 탐색을 하고 싶어하기 때문에 최소힙으로 사용해야 하는데, 파이썬의 heapq는 최소힙으로 구현이 되어 있기 때문에 바로 사용이 가능하다.

BFS때와 비슷하게, 큐에 시작 정점을 넣어주고 while 문을 사용하여 추후 인접 노드들을 탐색한다.

        if current_distance > distances[current_node]:
            continue

만약 우리가 확인하고자 하는 노드로의 거리가 이미 현재 테이블에 기록된 거리보다 크다면 건너뛴다.

    for neighbor, weight in graph[current_node].items():
                distance = current_distance + weight

앞서 말한 인접 노드를 확인하는 부분이다. current_distance + weight을 해주는 부분은, A 노드를 통해 B 노드로 탐색하는 경우 시작점 -> A의 가중치와 A -> B의 가중치를 더해야 하기 때문이다.

if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

만약 이렇게 더해진 가중치(거리)가 최단거리 테이블에 있는 기존값보다 적으면 새로 갱신한다. 추가적으로, 해당 경로를 사용해서 다른 정점으로 가는 방법이 최단경로일 수 있으니 해당 정점을 우선순위 큐에 넣어준다.

예제

특정 거리의 도시 찾기

import sys
import heapq
input = sys.stdin.readline
INF = float("inf")

def dijkstra(start, arr):
    distances = [INF for _ in range(len(arr))]
    distances[start] = 0 
    hq = [(0, start)] #이동한 거리와 현재 정점 정보

    while hq: 
        current_dist, current_node = heapq.heappop(hq)
        
        if current_dist > distances[current_node]:
            continue  

        for next in arr[current_node]:
            distance = current_dist + 1
            if distance < distances[next]:
                distances[next] = distance
                heapq.heappush(hq, (distance, next))
    
    return distances


N, M, K, X = map(int, input().split()) #정점의 개수, 간선의 개수, 목적지 거리, 출발지점  
adj = list([] for _ in range(N+1))


for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)

table = dijkstra(X, adj)

result = []
for i in range(1, N + 1): 
    if table[i] == K:
        result.append(i)

if result:
    for city in sorted(result):
        print(city)
else:
    print(-1)