[ 다익스트라 알고리즘] Dijkstra 기본

최단경로 문제

1) 단일 시작점 최단 경로 문제
: 출발점에서 다른 모든 정점들에 이르는 최단 경로를 구하는 문제

- 다익스트라 알고리즘 음의 가중치 허용하지 X,
- 델만포드 알고리즘 음의 가중치 허용, 가중치 합이 음인 사이클은 허용하지 않음

2) 모든 쌍 최단 경로 문제
: 모든 정점 쌍 간의 최단 경로를 구하는 것, 플로이드-워샬 알고리즘(동적 계획법)

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

1753번: 최단경로

백준 1753. 최단경로 풀이

import sys
import heapq

input = sys.stdin.readline

V, E = map(int, input().split())
start_node = int(input())

INF = int(1e9)

graph = [[] * (V+1) for _ in range(V+1)]
distance = [INF] * (V+1)

for _ in range(E):
    v1, v2, w = map(int, input().split())
    graph[v1].append((v2, w))


def dijkstra(start_node):
    q = []
    start_weight = 0
    heapq.heappush(q, (start_weight, start_node))
    distance[start_node] = 0

    while q:
        cur_cost, cur_node = heapq.heappop(q)

        if distance[cur_node] < cur_cost:
            continue

        for next_node, next_weight in graph[cur_node]:
            total_cost = cur_cost + next_weight
            if total_cost < distance[next_node]:
                distance[next_node] = total_cost
                heapq.heappush(q, (total_cost, next_node))


dijkstra(start_node)

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

아래의 두 자료형을 이용하여 현재 탐색한 것(heapq 활용)이 최소 거리에 영향을 주는지 확인한다.

graph = [[] * (V+1) for _ in range(V+1)]
distance = [INF] * (V+1)

 

distance 자료형은 각 노드들이 가지는 최소 거리들의 집합으로 초기 값은 INF(무한)으로 선언하였다. 아래의 코드는 파이썬에서 무한을 표시하는 방법이다.

INF = int(1e9)

 

또한 heapq의 정렬 순서를 유지하기 위해 (가중치, 다음 노드)의 자료구조를 선정하였다.

    while q:
        weight, node = heapq.heappop(q)

        if distance[node] < weight:
            continue

        for n, w in graph[node]:
            cost = weight + w
            if cost < distance[n]:
                distance[n] = cost
                heapq.heappush(q, (cost, n))

 

결론적으로, 다익스트라 단위 함수는 다음과 같다.

def dijkstra(start_node):
    q = []
    start_weight = 0
    heapq.heappush(q, (start_weight, start_node))
    distance[start_node] = 0

    while q:
        weight, node = heapq.heappop(q)

        if distance[node] < weight:
            continue

        for n, w in graph[node]:
            cost = weight + w
            if cost < distance[n]:
                distance[n] = cost
                heapq.heappush(q, (cost, n))

 

 

✍heapq 관련 사용법은 아래의 링크 참조

https://ratataca.tistory.com/147

[파이썬 힙] Heapq 사용법