[AIGORITHM THEORY] DIJKSTRA (다익스트라) 개념정리

개념

특징

• 최단 경로 알고리즘 중 가장 많이 사용된다.
• 무방향 그래프, 방향 그래프 모두 적용 가능하다.
• 모든 간선은 음이 아닌 비용을 가져야 한다.
• 시작 정점부터 모든 다른 정점까지의 최단 경로를 구하는 알고리즘

원리

• 시작 정점(v) 에서, 정점(u)까지의 최단경로 dist[u]를 구해, 정점 u가 집합 S에 추가되면, 새로 추가된 정점u 에 의해 단축되는 경로가 있는지를 체크한다.
• 현제 알고있는 dist[w]를 새로 추가된 정점 u를 거쳐서 가는 dist[u]+cost[u][w]와 비교, 경로가 단축된다면 dist[w]를 경로값으로 수정하면서 최단 경로를 찾는 알고리즘 이다.

dist[w] = min(dist[w], dist[u]+cost[u][w])

dijkstra(G, v)
    S ← {v}

    for i←0 to |V(G)|-1 do
        dist[i] ← cost[v][i]
        if cost[v][i] ≠ ∞ then
            pred[i] ← v
        else
            pred[i] ← NULL

    for(i←0; S!= V(G); i←i+1) do
        u ← S에 속하지 않은 정점 중에서 dist[]가 최소인 정점
        S ← S U {u}
        for(w←0; w∈V(G); w←w+1) do
            if(w∉S and dist[u]+cost[u][w]<dist[w]) then
                dist[w] ← dist[u]+cost[u][w]
                pred[w] ← u

end dijkstra()

힙을 사용한 알고리즘

• Priority Queue (우선순위 큐) : 우선순위가 높은 데이터를 가장 먼저 삭제
• 파이썬에서 우선순위 큐가 필요할 경우
  • 일반적으로 heapq 라이브러리 사용
  • Min Heap : 값이 낮은 데이터가 먼저 삭제
  • Max Heap : 값이 큰 데이터가 먼저 삭제 / heapq 라이브러리에서는 기본적으로 Min Heap 구조 사용

  def dijkstra(start):
      q = []
      # 시작노드로 가기 위한 최단 경로는 0으로 설정하며 힙에 삽입
      heapq.heappush(q, (0, start))
      distance[start] = 0
      while q: # 힙이 비어 있지 않다면
          # 가장 최단 거리가 짧은 노드 정보 꺼내기
          dist, u = heapq.heappop(q)
          # 현재 노드가 이미 처리된 적 있는 노드라면 무시
          if distance[u] < dist:
              continue
          # 현재 노드와 연결된 다른 인접 노드들 확인
          for i in graph[u]:
              cost = dist + i[1]
              if cost < distance[i[0]]: # relaxation
                  distance[i[0]] = cost
                  heapq.heappush(q, (cost, i[0]))
  
  dijkstra(start)
  # 모든 노드로 가기 위한 최단 거리 출력
  for i in range(1, n+1):
      if distance[i] == INF:
          print('INFINITY')
      else:
          print(distance[i])
  

시간복잡도

• O(V^2)
• 힙 구조를 사용할경우 : O(VlogV)

---

필기

• [참고] C++에서는 Max Heap, Java에서는 Min Heap으로 우선순위 라이브러리가 구현되어 있음
• 다익스트라 알고리즘은 DP를 활용한 대표적인 최단경로 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알아낼 수 있다. 현실 세계에서는 음의 간건이 존재하지 않기 때문에, 현실에 사용하기 매우 적합한 알고리즘중 하나라고 할 수 있다.
• 다익스트라 알고리즘이 DP문제인 이유는 ‘최단 거리는 여러개의 최단 거리로 이루어져 있기 때문’ 이다. 작은 문제가 큰 문제의 부분집하게 속해있는것! 기본적으로 다익스트라는 하나의 최단거리를 구할때 그 이전까지 구헀던 최단거리 정보를 그대로 사용한다는 특징이 있다.
• 다익스트라에서 요구되는 연산은 크게 두가지다.
  1. 모든 간선을 탐색하는 과정
  2. 우선순위 큐를 조작하는 연산

예제 문제!

• 이코테 - 화성탐사
• https://velog.io/@xxwb__/이것이-코딩-테스트다-최단-거리-화성-탐사
• 백준 - 백준 18352 / 특정 거리의 도시 찾기
• https://www.acmicpc.net/problem/18352

---

코드

• 힙을 활용한 다익스트라 알고리즘

def dijkstra(start):
    q = []
    # 시작노드로 가기 위한 최단 경로는 0으로 설정하며 힙에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q: # 힙이 비어 있지 않다면
        # 가장 최단 거리가 짧은 노드 정보 꺼내기
        dist, u = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적 있는 노드라면 무시
        if distance[u] < dist:
            continue
        # 현재 노드와 연결된 다른 인접 노드들 확인
        for i in graph[u]:
            cost = dist + i[1]
            if cost < distance[i[0]]: # relaxation
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)
# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
    if distance[i] == INF:
        print('INFINITY')
    else:
        print(distance[i])

• 백준 18352 / 특정 거리의 도시 찾기

#<https://www.acmicpc.net/problem/18352>
#특정 거리의 도시 찾기
#18352

from collections import deque
import sys
input = sys.stdin.readline

# n = 도시개수 / m = 도로개수 / k = 거리 정보 / x = 출발도시 번호
n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[a].sort()
    graph[b].sort()

# print(graph)

# visit = [0] * n*n
visit = [-1] * (n+1)

def bfs(graph, start, visit, k):

    result = []
    
    que = deque()
    que.append(start)
    visit[start] = 0
    
    while que:
        start = que.popleft()

        for i in graph[start]:
            if visit[i] == -1:
                que.append(i)
                visit[i] = visit[start] + 1
        
            # if visit[i] == k:
            #     result.append(i)

    return visit

visit = bfs(graph, x, visit, k)

ans = []
for i in range(len(visit)):
    if visit[i] == k:
        ans.append(i)

if ans:
    for i in ans:
        print(i)
else:
    print(-1)

---

참고자료

• 감사하신 홍정희 교수님의 강의자료
• https://velog.io/@xxwb__/이것이-코딩-테스트다-최단-거리-화성-탐사
• https://m.blog.naver.com/ndb796/221234424646
• https://namu.wiki/w/다익스트라 알고리즘