최단 경로 (다익스트라(Dijkstra))

목차

다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다.
다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우)
벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능)
플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능)

다익스트라(Dijkstra)

• 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.
• 음의 가중치를 가진 간선이 없는 경우에만 사용할 수 있습니다.
• 다익스트라(Dijkstra)
  • 초기 설정 : 시작 정점의 거리 값을 0으로, 다른 모든 정점의 거리 값을 무한대로 설정합니다.
  • 업데이트 : 우선순위 큐가 빌 때까지 아래 과정을 반복합니다. (모든 정점이 방문될때까지)
    • 우선순위 큐(최소 힙)를 사용하여 아직 방문하지 않은 정점들 중에서 거리가 가장 짧은 정점을 찾습니다.
    • 해당 정점을 방문 처리하고, 해당 정점을 통과하는 경로를 사용하여 다른 정점들의 거리 값을 업데이트 합니다.
    • 새로운 거리 값이 이전의 거리 값보다 작으면, 우선순위 큐에 새로운 거리 값을 가진 정점을 추가합니다.
  • 참고
    • visited는 의미가 없습니다. 우선순위 큐는 가장 거리가 짧은 값부터 꺼내게 됩니다. 따라서 우선순위큐에서 특정 정점이 꺼내지게 된다면 가장 먼저 꺼내졌던 거리값으로 해당 노드의 distance가 저장될것입니다. 즉, distance 값이 업데이트 되었다면 visited 처리가 된것입니다.(처음 inf값이 업데이트 되었다면 해당 노드는 더이상 업데이트 되지 않을 것입니다.)
  • 시간복잡도는 O((V+E)logV)입니다. (또는 O(ElogV))

• 코드

  • from heapq import heappush,heappop
    
    def dijkstra(graph, start):
        q = []
        answer = [float('inf') for _ in range(v+1)]
        heappush(q,(0,start))
        while q:
    
            now_weight,now_node = heappop(q)
            if answer[now_node]==float('inf'):
                answer[now_node]=now_weight
            else:
                continue
            
            for next_node,weight in graph[now_node]:
                if answer[next_node]==float('inf'):
                    heappush(q,(now_weight+weight,next_node))
                    
        return answer[1:]

  • 시간복잡도가 왜 O((V+E)logV)인지 살펴보도록 하겠습니다.
    • O(logV)는 우선순위 큐에서 나오는 시간복잡도입니다. 우선순위 큐에 값을 꺼내거나(값만 꺼낼 때는 O(1)의 시간복잡도이지만, 값을 꺼내고 난 뒤 남은 힙의 구조를 유지하기 위해 재배치 과정에서 O(logV)의 시간복잡도가 걸립니다.) 넣을 때 O(logV)가 걸리게 됩니다.
      • 근데 여기서 궁금한 점이 생깁니다. 특정 노드가 이미 우선순위 큐에 들어가서 대기 중이지만, 새로운 노드의 간선에 의해서 그 특정 노드에 대한 거리가 더 짧은 값이 우선순위 큐에 또 들어올 수가 있습니다. 그럼 왜 logE가 아닌 logV일까요? 
      • 이는 모든 노드들이 연결되어 있다고 가정하면, E=V^2이 됩니다. 그러면 이제 logE는 log(V^2)가 될 수 있습니다. 로그 성질에 의하여 log(V^2)은 2logV가 되므로 시간복잡도로 표현하면 O(logV)가 되는 것입니다.
    • 이제 모든 간선이 우선순위 큐에 들어갈지 말지 체크가 되기 때문에 최악의 경우 Elog(V)가 걸리게 됩니다. 
    • 마찬가지로 이제 우선순위 큐에서 각 노드들을 heappop을 하게 되므로 Vlog(V)가 걸리게 됩니다.
    • 따라서 시간복잡도는 O((V+E)logV) 가 됩니다. 하지만 일반적으로 E가 V보다 크기 때문에 간단하게 O(ElogV)로 표현합니다. (단, 그래프를 인접 리스트로 구현했을 때입니다. 인접리스트가 아닌 인접 행렬로 주어져있다면, 매번 인접한 정점을 찾아야 하니 E가 아니라 V^2이 걸리게 될 것입니다.)

예시

• 백준 1753 최단경로 문제를 살펴보겠습니다.
• 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구해야하는 문제입니다. 가중치는 자연수라고 명시가 되어져 있기때문에 다익스트라 알고리즘을 이용해 풀어야 한다는 것을 알 수 있습니다.
• 코드

  • import sys
    from heapq import heappush,heappop
    
    input  = sys.stdin.readline
    
    v,e = map(int,input().split())
    
    start_node = int(input())
    
    graph = [[] for _ in range(v+1)]
    
    for _ in range(e):
        a,b,w = map(int,input().split())
        graph[a].append((b,w))
        
    
    def dijkstra(start):
        q = []
        answer = [float('inf') for _ in range(v+1)]
        heappush(q,(0,start))
        while q:
    
            now_weight,now_node = heappop(q)
            if answer[now_node]==float('inf'):
                answer[now_node]=now_weight
            else:
                continue
            
            for next_node,weight in graph[now_node]:
                if answer[next_node]==float('inf'):
                    heappush(q,(now_weight+weight,next_node))
                    
        return answer[1:]
    
    answer = [item if item!=float('inf') else 'INF' for item in dijkstra(start_node)]
    for item in answer:
        print(item)