Algorithm. 그래프 - 다익스트라 알고리즘

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

SW Expert Academy

1. 최단 경로

• 간선의 가중치가 있는 directed graph가 있을 때,
• 두 정점 사이의 경로들 중 간선의 가중치가 합이 최소인 경로
• 단일 시작점 최단 경로 문제
  • 출발점에서 다른 모든 정점들에 이르는 최단경로를 구하는 문제
  • 다익스트라 알고리즘 : 음의 가중치 허용 안함.
  • 밸만 포드 알고리즘 : 음의 가중치 허용, 음의 사이클은 허용 안함
• 모든 쌍 최단 경로 문제
  • 모든 정점 쌍 간의 최단 경로를 구하는 문제
  • 플로이드-워샬 알고리즘 : 동적계획법 이용

2. 다익스트라 알고리즘

• 시작 정점에서 거리가 최소인 정점부터 선택해 나가면서 최단 경로를 구하는 방식
• 최소 신장 트리를 구하기 위해 정점을 하나씩 선택해나가는 프림 알고리즘과 동작 과정이 유사하다.
• 그리디 알고리즘을 이용한다.
  • 정점 r에서 정점 t까지의 최단 경로 중간에 정점 x가 존재할 때,
  • r~t까지의 최단 경로는 r~x까지의 최단경로와 x~t까지의 최단 경로로 구성된다.

3. 예시

• 그래프 r에서 t까지의 최단 경로 : r - w - x - t
• 최단 경로 상에 x가 있어 r~x 까지의 최단 경로 : r - w - x
• 출발점 r에서 정점 v까지의 최단 경로 가중치 합 : d[v]

정점 r ~ 정점 t 까지의 최단 경로

• r~t 까지의 최단 경로
• d[y] + 간선 y~t 가중치
• d[x] + 간선 x~t 가중치
• 둘을 비교한다. 

정점 r ~ 정점 x 까지의 최단 경로

• r~x 까지의 최단경로
• r에서 x로 바로 가능 가중치
• y 또는 w를 거쳐서 가능 경로
• 셋 중 가중치 합이 최소인 경로

그래서 다익스트라 알고리즘은

• 시작점에서 최단경로를 찾은 정점들의 집합 S와 최단 경로를 찾지 못한 정점들의 집합을 관리한다.
• 최초 S = { 시작정점r }, d[r] = 0, d[v] = ∞ ( v ∈ V - U )
• 최단 경로를 찾은 정점을 하나씩 집합 S에 추가
• 집합 S에 포함되지 않은 정점들(최단 경로를 찾지 못한 정점들의 집합) 중에 출발점에 가장 가까운 정점 선택

그리디 알고리즘 적용

소스코드

# D : 출발점에서 각 정점까지 최단 경로 가중치 합을 저장
# P : 최단 경로 트리 저장
# G : 그래프
# r : 시작 정점

def dijkstra(G, r):
    D = [INF] * N
    P = [None] * N
    visited = [False] * N # 각 정점 방문여부
    D[r] = 0 # 출발점 가중치 0
    
    for _ in range(N): # 정점 개수만큼 반복
    	minIndex = -1
        min = INF
        for i in range(N): # 방문 안한 정점 중 최소 가중치 정점 찾기
            if not visited[i] and D[i] < min:
            	min = D[i]
                minIndex = i
        visited[minIndex] = True # 최소 가중치 정점을 찾아서 방문처리
        for v, val in G[minIndex]: # 최소 가중치 정점의 인접 정점들에 대해서 반복
            if not visited[v] and D[minIndex] + val < D[v]: # 방문 안한 정점 중 minIndex 정점을 경유해서 방문하는 가중치가 더 작으면 갱신한다.
            	# 즉 minIndex 정점을 경유해서 가는 것이 기존의 출발점에서의 가중치보다 더 작은지 비교하는 코드
            	D[v] = D[minIndex] + val
            	P[v] = minIndex # 이전 경로 갱신

 

4. 밸만-포드 알고리즘

동적 계획법 적용