동빈나 2021 이코테 _ 7. 최단경로 알고리즘 ( 다익스트라)

최단경로 알고리즘이란, 가장 짧은 경로를 찾는 알고리즘

• 다양한 문제상황
  • 한지점에서 다른 한지점
  • 한 지점에서 다른 모든지점
  • 모든 지점에서 다른 모든지점
• 각 지점은 그래프에서 노드로 표현하고 지점간 연결된 도로는 간선으로 표현함
  • ex ) 마을과 마을을 있는 도로, 도시를 있는 통로 등등

---

1. 다익스트라 알고리즘

• 특정한 노드(출발노드)에서 다른모든 노드로 가는 최단경로를 계산 (음의간선이 없을때)
• 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (일종의 그리디 알고리즘)
• 동작과정 
  • 출발노드를 설정
  • 최단거리 테이블을 초기화 (자기자신을 제외한 모든노드까지의 거리를 무한대로 설정, 자기자신은 0)
  • 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 ( 이 과정을 통해 특정 노드까지의 최단거리를 확정짓는것이므로, 모든반복이 끝났을때 전체노드까지의 최단거리가 나오게되는것
  • 해당노드를 거쳐 다른 노드로 가는 비용을 계산해 테이블을 갱신한다
  • 위과정에서 3,4번을 반복한다.
• 최단거리 테이블은 각 노드에 대한 현재까지의 최단거리 정보를 가지고있음
• 처리과정에서 더 짧은경로를 찾으면 "이게 더 짧은 경로야"라고 갱신하는것

 

• 방문하지 않은것중 거리가 짧은것을 선택한다. -> 1번노드를 선택
• 1번노드를 거쳐갈때의 비용 vs 현재비용 (테이블의 비용) 후 짧은것으로 갱신

 

• 2번, 3번, 4번노드의 거리가 갱신됨
• 갱신이 완료되었으므로 다시 반복한다. 거리가 가장 짧은노드인 4번노드를 선택한후 반복 --> 4번노드까지의 최단거리는 이제 더이상 변하지 않는다!! 
• 따라서 4번노드를 거쳐갈때의 최단경로는 현재 4번까지의 최단경로 + 4번에서부터 출발하는 거리 

 

• 이때 4번노드는 이미 방문이 된 노드이므로(=이미 최단거리가 확정된 노드) 건너뛰어도 된다.

마지막노드에 대한 처리는 하지 않아도 됨 -> 이미 최단경로가 모두 결정되었기때문

 

다익스트라 알고리즘의 특징

• 단계를 거치며 한번 처리된 노드의 최단거리는 고정되어 더이상 바뀌지 않음
• 그리디 알고리즘 - 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복함
• 한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는것으로 이해할 수 있음

 

1.1) 다익스트라 알고리즘 구현

 

1. 간단한 방법

import sys
input = sys.stdin.readline

INF = int(1e9)

n, m = map(int, input().split())
start = int(input())

graph = [[] for _ in range(n+1)] #0번은 취급하지 않기위해 n+1길이만큼 생성 -> 노드연결정보

visited = [False]* (n+1) # 방문정보
distance = [INF] * (n+1) # 최단거리테이블

#모든 간성정보를 입력받기
for _ in range(n):
    a,b,c = map(int, input().split())
    graph[a].append((b,c)) #a에서부터 b까지 가는 거리가 c다

def get_smallest_node():
    min_value = INF
    index = 0 # 현재 가장 짧은거리를 갖는 노드의 인덱스를 저장
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]: #테이블중에서 방문되기 전 노드중 가장짧은거리를 가지는
            min_value = 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(n-1): #시작노드를 제외한 n-1개의 노드에 대해 반복
        now = get_smallest_node()
        visited[now] = True

        for j in graph[now]: #now번째 인덱스 노드와 연결된 노드와 거리 ( 노드, 거리)
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

• 성능분석 - O(v)번에 걸쳐서 매번 선형탐색하므로 시간복잡도는 O(v^2)이다.
• 전체노드개수가 5천개 이하라면 해결가능하지만 노드가 10000개이상이면 더 효율적인 알고리즘이 필요함

 

 

2. 우선순위큐 (Priority Queue)

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 예를들어 여러개의 물건데이터를 자료구조에 넣었다가 가치가 높은물건부터 꺼내서 확인해야 하는경우 
• 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원
• 우선순위 큐 구현방식에는 리스트(삽입,삭제:O(1),O(N))를 이용한 방법과 힙(O(longN))을 이용한 방법이 있다.

 

2.1) 힙

• 우선순위큐를 구현하기 위한 자료구조
• 최소힙 / 최대힙

기본이 최소힙

• hepppush() : 특정 리스트에 어떤 데이터를 넣을때
• heappop() : 특정리스트에서 데이터를 꺼낼때 -> 우선순위대로 꺼내짐 (기본은 min hip이므로 우선순위가 낮은원소부터 꺼내짐)
• 따라서 default는 오름차순으로 꺼내진다.

• 최대힙을 이용하고싶을때는 부호를 바꿔서 넣은뒤, 꺼낼때 다시 부호를 바꿔주면됨

• 반복과정은 동일하지만 선택하는 과정에서 효율적으로 하게하기 위해서 거리를 기준으로 힙에 넣는다.

힙을 이용한 우선순위 큐를 이용한 다익스트라 알고리즘 동작과정

큐에 넣을때 튜플형식으로 넣되 첫번째 원소값을 거리로 설정하면 최소힙을 사용할때 거리가 짧은순으로 가져올수있다.

• 큐에 담겨있는 원소 (0,1) -> 꺼내고 방문처리한다. 해당노드와 인접한 노드의 거리를 갱신하고 우선순위큐에 다시 넣는다.
• 큐에 담겨있는 원소 (1,4), (2,2), (5,3) -> 꺼내고 방문처리한다.

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)] #0번은 취급하지 않기위해 n+1길이만큼 생성 -> 노드연결정보

# 최단거리테이블을 모두 무한으로 초기화
distance = [INF] * (n+1) # 최단거리테이블

#모든 간성정보를 입력받기
for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c)) #a에서부터 b까지 가는 거리가 c다

# 다익스트라 알고리즘 - 방문처리여부를 확인 필요X
def dijkstra(start):
    q = []
    
	#시작 노드로 가기위한 최단경로는 0으로 설정하고 (우선순위)큐에 삽입
    heapq.heappush(q,(0, start)) 
    distance[start] = 0

	# 큐가 빌때까지
    while q:
        dist, now = heapq.heappop(q) # 거리가 가장 짧은 노드를 큐에서 꺼낸다.
        # 현재 노드가 이미 처리된적 있는 노드라면 무시 -> 방문이 되었는지 확인하는것과 같은원리
        # 현재 꺼낸 그 원소의 거리값(dist)이 테이블에 기록되어있는 값보다 더 크다면 이미 처리된것
        if distance[now] < dist:
        	continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]: #현재노드를 거쳐가는것과 기존의 값을 비교
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

• 성능분석 - 힙자료구조를 사용하는 다익스트라 알고리즘의 시간복잡도 O(ElogV)
• 직관적으로는 시간복잡도를 O(ElogE)로 생각할 수 있다.