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

목차

• 다익스트라 알고리즘 소개
• 알고리즘 동작 과정
• 알고리즘 구현(파이썬)

 

 

 

다익스트라(Dijkstra) 최단 경로 알고리즘

• 특정 정점에서 출발하여 다른 모든 노드로 가는 최단 경로 계산
• Single-Source Shortest Paths 문제에 사용될 수 있음
• 매 상황에서 가장 비용이 적은 노드 선택을 반복(그리디 알고리즘)

 

 

 

 

알고리즘 동작 과정

1. 출발 정점 선택
2. 최단 거리 테이블을 INF로 초기화
3. 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점 선택
4. 해당 정점을 거쳐 다른 정점으로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3~4번 과정 반복

 

 

 

 

 

 

알고리즘 구현

방문하지 않은 정점 중에 최단 거리가 가장 짧은 정점을 빠르게 찾기 위해 우선순위 큐 사용

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 정점의 개수, 간선의 개수 입력
n, m = map(int, input().split())
# 시작 정점 입력
start = int(input())
# 인접 리스트 생성
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블 초기화
distance = [INF] * (n + 1)

# 인접 리스트 초기화
for _ in range(m):
    i, j, c = map(int, input().split())
    graph[i].append((j, c)) # 정점 i에서 정점 j로 가는 비용 c

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))   # 시작 정점 삽입
    distance[start] = 0
    while q:
        # 최단 거리가 최소인 정점의 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 이미 방문한 정점인지 확인
        if distance[now] < dist:
            continue
        # 현재 정점과 인접한 정점 확인
        for x in graph[now]:
            new_dist = dist + x[1]
            # 현재 정점을 거쳐가는게 거리가 더 짧을 경우 최단 거리 테이블 갱신
            if new_dist < distance[x[0]]:
                distance[x[0]] = new_dist
                heapq.heappush(q, (new_dist, x[0]))

dijkstra(start) # 다익스트라 알고리즘 수행

# 최단 거리 테이블 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우 INF 출력
    if distance[i] == INF:
        print("INF", end=" ")
    else:
        print(distance[i], end=" ")

 

위와 같은 그래프를 입력으로 넣을 경우 0 5 4 2 1 출력

 

 

 

 

참고

• github.com/ndb796/python-for-coding-test
• Foudations of Algorithms