Logseq/pages/다익스트라 알고리즘 (Dijkstra Algorithm).md

deck:: Logseq/coding tip

• 1. 개념(Concept)

  • 그래프의 특정 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘.
  • 특징
    • {{cloze 음의 가중치}}가 있는 간선이 있으면 사용할 수 없음. extra:: 음의 가중치가 있을 경우에는 벨만-포드 알고리즘 (Bellman-Ford Algorithm)을 사용 id:: 695394f8-cd61-4d4b-9fbc-1cba54ba0195
    • 그리디(greedy)방식을 사용하며, 매 단계에서 {{cloze 현재 갈 수 있는 가장 가까운 정점}}을 확정한다. id:: 695395cf-75da-45ea-a7d4-259f5d3d942b

• 2. 동작 원리 (Algorithm Flow)

  • 1. 초기화 : 시작 정점의 거리는 0, 나머지 모든 정점의 거리는 무한대로 설정한다. id:: 6953966b-74ec-4cc0-af49-ab5754b3bb80 #+BEGIN_EXTRA

    INF = sys.maxsize # float("inf")
    dist = [INF] * (v + 1)
    dist[start_node] = 0
    

    #+END_EXTRA
  • 2. 우선순위 큐를 생성하고 그곳에 {{cloze (거리: 0, 노드: 시작정점)}} 을 넣는다. #card id:: 6953968c-552b-41a5-af23-628736952cac #+BEGIN_EXTRA

    pq = [(0, start_node)]
    

    #+END_EXTRA
  • 3. 큐가 빌 때까지 아래의 과정을 반복한다. id:: 695396a3-2c9b-4bf5-a292-0cb14b2395fe (초기화 및 초기 생성을 마친 뒤 반복문 부분의 코드를 답변할 것) #card

    • while pq :
        	# 가장 최단 거리가 짦은 노드 꺼내기
          curr_dist, curr_node = heapq.heappop(pq)
      
          # 이미 처리된 적 있는 노드라면 무시 (더 짦은 경로가 이미 발견됨)
          if dist[curr_node] < curr_dist :
            	continue
      
          # 인접 노드 확인
          for next_weight, next_node in graph[curr_node] :
            	# 현재 노드를 거쳐서 가는 거리
            	new_dist = next_weight + curr_dist
      
              # 현재 노드를 거쳐서 가는 거리가 기존 거리보다 짦다면 갱신
              if new_dist < dist[next_node] :
                	dist[next_node] = new_dist
                  heapq.heappush(pq, (new_dist, next_node))
      

  • 4. 종료: 모든 정점에 대한 최단거리가 확정된다.

• 3. 코드 (python)

  • import heapq
    import sys
    
    # INF: 무한대 값 설정 (초기화용)
    INF = sys.maxsize
    
    def dijkstra(start_node, v, graph):
        # 1. 최단 거리 테이블 초기화 (모두 무한대)
        dist = [INF] * (v + 1)
    
        # 2. 시작 정점 설정
        dist[start_node] = 0
        # (거리, 정점) 순서로 큐에 삽입 (거리가 작은 순서대로 꺼내기 위함)
        pq = [(0, start_node)]
    
        while pq:
            # 3. 가장 최단 거리가 짧은 노드 꺼내기
            curr_dist, curr_node = heapq.heappop(pq)
    
            # 4. 이미 처리된 적 있는 노드라면 무시 (더 짧은 경로가 이미 발견됨)
            if dist[curr_node] < curr_dist:
                continue
    
            # 5. 인접 노드 확인
            for next_weight, next_node in graph[curr_node]:
                # 현재 노드를 거쳐서 가는 거리가 더 짧은 경우
                new_dist = curr_dist + next_weight
    
                if new_dist < dist[next_node]:
                    dist[next_node] = new_dist
                    heapq.heappush(pq, (new_dist, next_node))
    
        return dist
    
    

• 4. 시간복잡도

  • {{cloze $O(E\log V)$}} extra:: E : 간선 갯수, V : 정점 갯수 id:: 6953bf9f-bc68-4829-a2ba-a884cd15a9e8