다익스트라(Dijkstra)

최단경로에 대한 개괄적인 설명

• 간선의 가중치가 양수인 경우
  • Dijkstra는 정점을 지날수록 가중치가 증가한다는 사실을 전제한다.
  • Dijkstra는 집합(S)에 들어간 노드는 다시 고려하지 않는다.

• 임의의 단일 시작점에서부터 최단 경로 찾기

• Prim 알고리즘과 원리가 유사, Greddy 알고리즘 기반 또는 Dynamic Programming이기도 함

• 기본 시간복잡도는 $O(V^2)$ 이지만, Prim과 마찬가지로 이진힙을 사용 시 $O(E\log V)$다.

초기화

• 노드 집합 S 초기화 (방문 여부 확인 목적의 집합)

  • $S=V(G)$ : 그래프 G의 전체 정점 집합
  • $S = \{r\}$ : 시작 정점 r이 들어있는 집합

  둘 중 하나를 선택

• 거리 초기화

  시작 노드 r에서 다른 노드 w 사이의 거리($y_w$) 초기화

  노드 r과 연결되지 않은 노드들의 거리는 모두 $\infty$(파이썬의 경우 sys.maxsize)로 설정

루프

Step 1.

• 집합 S 노드와 인접한 노드 중 최단 거리를 가진 노드 v를 찾아서 S에서 제거 또는 추가

• 노드 v에 인접한 노드 w에 대해서 다음 조건을 검사한다.

  \[y_w=y_v+c_{vw}, \,\,if\,\,y_v+c_{vw}<y_w\]

​

​ (relax 연산이며 노드 w는 S에 포함된 노드 또는 포함되지 않은 노드)

Step 2.

• 집합 S에 모든 노드가 제거될 때까지 또는 모든 노드가 포함 될 때까지 Step 1을 반복

• 방문이 한 번 완료된 정점까지의 거리값은 변하지 않는다.

Source code

1. $O(N^2)$

import sys
INF = sys.maxsize #무한대의 역할로 사용할 값
'''
N : 그래프 내 정점의 개수 len(g); start = 0
g : 그래프의 인접행렬을 담은 이차원 리스트 [[(인접 노드,간선 가중치),(),...],...]
D : 거리 [infinity]*N; D[start]=0
previous : 선행(부모) 노드를 기록 (경로 저장) [None]*N
visited : 방문 여부를 기록 [False]*N
'''
def dijkstra(g : list, D : list, visited : list, previous : list, N : int) :
    for i in range(N) :
        m = -1 #이전 노드의 index
        min_value = INF #매 갱신마다 무한대 값으로 초기화
        for j in range(N) :
            if not visited[j] and D[j] < min_value : #처음에는 j가 start가 되는 경우를 제외하고 D[j]와 min_value가 infinite이므로 pass가 된다.
                min_value = D[j] #최소값을 갱신
                m = j #최소값을 가지는 노드의 인덱스를 현재 노드로 저장
        visited[m] = True #집합 S에 노드를 포함
        #인접 노드의 선행(부모)노드 및 거리비용 갱신
        for destination, cost in g[m] : #현재 노드 인덱스 m이 가지는 (destination, cost(weight)) 쌍에 대해서 반복 
            if not visited[destination] :
                if D[m] + cost < D[destination] : #Step 1의 조건식
                    D[destination] = D[m] + cost
                    previous[destination] = m
            	

2. $O(E\log V)$ : heapq 사용, 시작점, 끝점이 주어진 경우

from heapq import *
from collections import *
'''
D : (출발, 도착, 가중치)로 이루어져 그래프를 표현한 일차원 배열
s : start
t : target
'''
def dijkstra(D,s,t):
    g = defaultdict(list)
    for l,r,c in D : #left #right #cost
        g[l].append((c,r)) #인접행렬 생성
    
    q, seen, mins = [(0,s,())],set(),{s: 0} 
    # q : [(0,s,())] = [(누적 cost, 현재 index, 경로)]
    # seen : 방문노드
    # mins : 각 노드별 저장된 최소 경로 값
    while q :
        (cost,v1,path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1,path)
            if v1 == t :
                return (cost, path)
            
            for c,v2 in g,get(v1,()):
                if v2 in seen :
                    continue
                prev = mins.get(v2,None)
                next = cost + c
                if prev is None or next < prev:
                    mins[v2] = next
                    heappush(q, (next,v2,path))
    return float("inf")

참고 자료

• https://vegatrash.tistory.com/69
• 학부 수업 강의록