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

: 한 노드에서 다른 노드로 가는 각각의 최단경로 구하기

특징

• 간선의 가중치는 양수여야 한다.

• 그리디로 분류된다.
  → 매번 가장 비용이 적은 노드 선택

• 최단 거리 테이블 : 각 노드에 대한 현재까지의 최단 거리 정보 저장 → 계속 갱신

동작 원리

"방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택"을 반복하기

초기 상태

출발 노드 : 1

→ 모든 최단 거리를 무한(1e9)으로 초기화

Step 0 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택

→ 출발노드~출발노드는 0이므로 1번 노드 선택

Step 1 현재 노드에서 다른 노드로 가는 비용 계산

현재 노드인 1번 노드를 거쳐 다른 노드로 가는 비용 계산

Step 2 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 4번 노드

4번 노드를 거쳐 다른 노드로 가는 비용 계산

Step 3 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 2번 노드

Step 4 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 5번 노드

Step 5 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 3번 노드

Step 6 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 6번 노드

→ 최종 최단 거리 테이블

: 1번 노드에서 출발했을때, 2번까지 2, 3번까지 3, 4번까지 1, 5번까지 2, 6번까지 4라는 의미

구현

방법 1) 간단한 다익스트라 알고리즘

• 매번 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 탐색하기 위해 최단 거리 리스트 순차 탐색
• 시간 복잡도 : $O(V^2)$ → V는 노드의 개수
  → 일반적으로 전체 노드의 개수가 5000개 이하일때만 사용 가능

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

n, m = map(int, input().split()) #노드 개수, 간선 개수
start = int(input()) #시작 노드
graph = [[] for _ in range(n+1)] #노드 연결 정보
visited = [False]*(n+1) #방문 여부 체크 배열
distance = [INF]*(n+1) #최단 거리 테이블

for _ in range(m):
    a,b,c = map(int, input().split()) #a->b의 비용 c
    graph[a].append((b,c))

#방문하지 않은 노드 중, 최단거리가 가장 짧은 노드 찾기
def get_smallest_node():
    min_val = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_val and not visited[i]:
            min_val = distance[i]
            index = i
    return index

def dijkstra(start):
    #시작 노드 처리
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]

    for i in range(1, n-1):
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

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

방법 2) 개선된 다익스트라 알고리즘

• 가장 최단거리가 짧은 노드를 선형적으로 찾는게 아닌 Heap을 이용해서 처리

→ 우선순위 큐에 더 짧은 경로를 찾은 노드 넣고, 꺼낼때는 해당 노드를 방문한 적이 있으면 무시, 아니면 처리해주면 된다.

• 시간 복잡도 : $O(ElogV)$ → V는 노드의 개수, E는 간선의 개수

→ Heap이란? [Python] Heap을 참고

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

n, m = map(int, input().split()) #노드 개수, 간선 개수
start = int(input()) #시작 노드
graph = [[] for _ in range(n+1)] #노드 연결 정보
distance = [INF]*(n+1) #최단 거리 테이블

for _ in range(m):
    a,b,c = map(int, input().split()) #a->b의 비용 c
    graph[a].append((b,c))

def dijkstra(start):
    #시작 노드 처리
    pq = []
    heapq.heappush(pq, (0, start))
    distance[start] = 0

    while pq:
        dist, now = heapq.heappop(pq)

        #현재 노드가 이미 처리된 적 있는 노드면,
        if distance[now] < dist:
            continue
        #아니면,
        for i in graph[now]:
            cost = distance[now] + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(pq, (cost, i[0]))

dijkstra(start)

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

출처

나동빈님의 이것이 취업을 위한 코딩테스트다