[ 다익스트라 ] 알고리즘

 

 

1.   개념

 

다익스트라 알고리즘 : 그래프에서 출발 노드와 출발 노드 이외의 모든 노드들과의 최단 거리를 구하는 알고리즘

조건 : 에지는 항상 양수

시간 복잡도 : ElogV ( E : 에지 수 V : 노드 수 )

 

 

 

2.  다익스트라 구현

 

 

1 )  초기 설정

 

     (1)  인접 리스트 구현 - 인접 노드 혹은 (인접 노드, 가중치) 형식으로 구현 

     (2)  최단 거리 리스트 초기화 - 출발 노드는 0, 나머지 노드는 무한으로 초기화

     (3)  방문 리스트 초기화 - 같은 노드 여러번 방문하지 않도록

     (4)  우선순위 큐 생성

 

 

2 )  값이 가장 작은 노드 선택

     

     아직 방문하지 않은 노드들 중 최단 거리 리스트에서 값이 가장 작은 노드 선택 ( 우선순위 큐 이용 )

      -> 선택한 노드의 방문 리스트 체크

 

      왜 최단 거리 값이 가장 작은 노드를 선택해야 하는가?

       다익스트라는 노드의 최단 거리를 하나씩 확정해나가는 알고리즘인데

       어떤 노드의 최단 거리를 확정하는 거냐 하면...

       2 ) 단계에서 선택한 노드...!!

       그러고 나서 선택한 노드의 인접 노드들은 최단 거리를 업데이트

       즉, 1.(선택한 노드의 최단 거리 + 선택-인접 노드 간 에지 가중치)로 갱신 2. 현재 최단 거리 유지 중 하나가 선택된다

       이때 최단 거리 값이 가장 작은 노드(1.이 선택될 가능성이 가장 큰)를 선택해줌으로써

       더 작은 최단 거리 값으로 갱신할 수 있는지 확인하는 것이다

       

 

       사실 교재 보고 그냥 쓱 넘겼던 부분인데

       은채가 왜 우선순위 큐 써야 돼?? 의문을 던져줘서 고민하게 됨(천재만재 은채쒜)

       그리구 은채가 질문 게시판에 올린 글에 고수님이 댓글 달아준 거 보고 이해했당(천재만재 은채쒜)

 

 

3 )  최단 거리 리스트 업데이트

 

       선택한 노드의 인접 노드의 최단 거리 값을 업데이트

       min( 선택한 노드의 최단 거리 값 + 선택-인접 노드 에지 가중치, 인접 노드의 최단 거리 값 )

 

 

 

 

 

3.  문제

 

# 1  최단 경로 - 백준 1753번

https://www.acmicpc.net/problem/1753

1753번: 최단경로

import sys
from queue import PriorityQueue
input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())
distance = [sys.maxsize] * (V+1)  # 최소 거리 리스트
visited = [False] * (V+1)  # 방문 리스트
myList = [[] for _ in range(V+1)]  # 인접 리스트(노드, 가중치)
q = PriorityQueue()  # 우선순위 큐 -> 최소 거리 값이 가장 작은 것부터 선택하기 위함

# 인접 리스트 구현
for _ in range(E):
    u, v, w = map(int, input().split())
    myList[u].append((v, w))

# 시작 노드 넣기
q.put((0, K))  ->  우선순위 큐에서 get하는 기준은 최소 거리가 돼야 하므로 (최소거리, 노드)로 저장
distance[K] = 0

# 다익스트라
while q.qsize() > 0:
    current = q.get()
    c_v = current[1]
    # 아직 방문하지 않은 노드 선택
    if visited[c_v]:
        continue
    visited[c_v] = True

    for tmp in myList[c_v]:
        next = tmp[0]
        value = tmp[1]
        # 최소 거리 업데이트
        if distance[next] > distance[c_v] + value:
            distance[next] = distance[c_v] + value
            q.put((distance[next], next))

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

 

 

# 2  최소비용 구하기

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

import sys
from queue import PriorityQueue

input = sys.stdin.readline

n = int(input())
m = int(input())

visited = [False] * (n+1)
distance =[sys.maxsize] *(n+1)
node = [[] for i in range(n+1)]
q = PriorityQueue()

for i in range(m):
    u, v, c = map(int, input().split())
    node[u].append((v, c))
    
s, e = map(int, input().split())

q.put((0, s))
distance[s] = 0

while q.qsize() > 0:
    a = q.get()[1]
    if visited[a]:
        continue
    visited[a] =True
    
    for next in node[a]:
        dosi = next[0]
        cost = next[1]
        
        if distance[dosi] > distance[a] + cost:
            distance[dosi] = distance[a] + cost
        q.put((distance[dosi], dosi))
        
 
print(distance[e])

 

# 1 이랑 완전 같은 문제~~

 

# 3  K번째 최단경로 찾기

https://www.acmicpc.net/problem/1854

1854번: K번째 최단경로 찾기

import sys
import heapq
input = sys.stdin.readline

n, m, k = map(int, input().split())
graph = [[] for _ in range(n+1)]

#거리 리스트 -> 2차원 리스트로 초기화(k x (n+1))
#k번째 거리 찾기 위해서
distance = [[sys.maxsize] * k for _ in range(n+1)] 

#인접리스트 초기화 -> (노드, 가중치)
for i in range(m):
    u, v, d = map(int, input().split())
    graph[u].append((v, d))

#시작 노드 큐에 넣기 -> (가중치, 노드) : 기준이 가중치이므로
queue = [(0, 1)]
#시작 노드 거리 리스트 0으로 초기화
distance[1][0] = 0

#큐가 빌 때까지
while queue:
	#가중치 가장 작은 거 pop
    cost, node = heapq.heappop(queue)
    #pop한 노드의 인접 노드
    for next in graph[node]:
        next_node = next[0]
        next_cost = next[1]
        #k번째 최단 거리 업데이트
        #만약 next_node의 distance에 저장되어 있는 k번째 거리 > 현재 구한 거리 -> k번째 거리 갱신
        #현재 구한 거리 = cost + next_cost
        #cost: 현재 경로까지의 거리 / next_cost: 현재 노드에서 인접 노드까지의 거리
        if distance[next_node][k-1] > cost + next_cost:
            distance[next_node][k-1] = cost + next_cost
            distance[next_node].sort()
            #????????? 
            heapq.heappush(queue, (cost + next_cost, next_node))


for i in range(1, n+1):
    if distance[i][k-1] == sys.maxsize:
        print(-1)
    else:
        print(distance[i][k-1])

 

교재 보고 이해하는 중....

 

의문점

왜 next_node의 distance 배열의 k번째 값 > 현재 구한 거리(새로운 경로)를 만족하는 경우에만 큐에 노드를 삽입하는 거지??