다익스트라(Dijkstra) 알고리즘 (백준 문제 포함)

다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.

간선에 가중치가 없다면 너비 우선 탐색(BFS)으로도 충분히 풀 수 있지만, 간선에 가중치가 있다면 풀기가 매우

힘들어진다. 간선에 가중치가 있다면 다익스트라 알고리즘을 사용해서 풀도록 하자!!

다익스트라 알고리즘은 동작 과정은 아래와 같다.

1. 출발 노드 지정

2. 최단 거리 테이블 초기화

3. 방문한 적 없는 노드 중에서 최단 거리가 제일 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 거리를 구하여 최단 거리 테이블을 업데이트

5. 위 3, 4번 과정을 모든 노드를 방문할 때까지 반복

 

아래 코드는 파이썬으로 구현한 다익스트라 알고리즘 예시이다.

백준 1753번 최단경로)

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

V, E = map(int, input().split())
start = int(input())
INF = 10**9
dis = [INF]*(V+1)
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
dijkstra(start)
for n in dis[1:]:
    print(n if n != INF else "INF")

 

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/1011

백준 알고리즘 1753번 최단경로(python)

jinho-study.tistory.com/1013

백준 알고리즘 1504번 특정한 최단 경로(python)

jinho-study.tistory.com/1014

백준 알고리즘 1446번 지름길(python)

jinho-study.tistory.com/1015

백준 알고리즘 1916번 최소비용 구하기(python)

jinho-study.tistory.com/1021

백준 알고리즘 5972번 택배 배송(python)

jinho-study.tistory.com/1022

백준 알고리즘 14284번 간선 이어가기 2(python)

jinho-study.tistory.com/1023

백준 알고리즘 17396번 백도어(python)

jinho-study.tistory.com/1069

백준 알고리즘 1238번 파티(python)