[알고리즘] 다익스트라 알고리즘(최단거리 알고리즘)

유니·2022년 5월 22일
0

알고리즘

목록 보기
1/3

최단 경로 알고리즘

  • 가장 짧은 경로를 찾는 알고리즘을 의미한다.
  • 문제상황
    • 한 지점에서 다른 한 지점까지의 최단 경로
    • 한 지점에서 다른 모든 지점까지의 최단 경로
    • 모든 지점에서 다른 모든 지점까지의 최단 경로
  • 지점은 그래프에서 노드로 표현
  • 지점 간 연결된 도로는 그래프에서 간선으로 표현

다익스트라 최단 경로 알고리즘

  • 특정한 출발 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.

  • 음의 간선이 없을 때 정상적으로 동작한다. (=현실 세계의 도로)

  • 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문이다.

  • 동작과정
    다익스트라
    1️⃣ - 출발 노드를 설정한다.
    2️⃣ - 최단 거리 테이블을 초기화한다. (간선길이를 모두 무한으로 정의)
    3️⃣ - 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택한다.
    4️⃣ - 해당 노드를 거쳐가는 경우과 거쳐가지 않은 경우를 비교하여 최단거리 갱신한다.
    5️⃣ - 3️⃣, 4️⃣ 과정을 반복한다.

  • 간단한 구현 O(n²)
    단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)한다.

    n, m = map(int, input().split())
    INF = int(1e9)
    
    canSee = list(map(int, input().split()))
    
    graph = [[] for _ in range(n)]
    visited = [False] * (n)
    distance = [INF] * (n)
    
    for _ in range(m):
      a, b, t = map(int, input().split())
        graph[a].append((b, t))
    
    def get_smallest_node():
      min_value = INF
      index = 0
      for i in range(n):
        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 v in graph[start]:
        distance[v[0]] = v[1]
    
      for _ in range(n - 1):
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
          cost = distance[now] + j[1]
          if cost < distance[j[0]]:
            distance[j[0]] = cost
    
    dijkstra(0) # 시작노드 0
    
    print(distance[-1]) # 종료노드 n-1
  • 힙 자료구조로 구현 O(nlogn)
    단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용한다.

    import heapq
    n, m = map(int, input().split())
    INF = int(1e9)
    
    graph = [[] for _ in range(n)]
    distance = [INF] * (n)
    
    for _ in range(m):
      a, b, t = map(int, input().split())
        graph[a].append((b, t))
    
    def dijkstra(start):
      q = []
      heapq.heappush(q, (0, start))
      distance[start] = 0
      while q:
        dist, now = heapq.heappop(q)
        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(0)
    
    if distance[-1] == INF:
      print(-1)
    else:
      print(distance[-1])

참고 링크
https://haningya.tistory.com/116
https://www.youtube.com/watch?v=acqm9mM1P6o

profile
추진력을 얻는 중

0개의 댓글