[Code Tree] 그래프 알고리즘 - 다익스트라(Dijkstra)

[Dijkstra]

최단거리

* 가중치가 전부 동일하다면, 방향성이 있는 그래프와 없는 그래프에서 모두 BFS를 이용하여 최단거리를 구할 수 있다.

 

다익스트라 알고리즘

- 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘 

특정 지점까지 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리 

 

- 거리 배열을 전부 아주 큰 값(INF)으로 초기화하고, 출발지의 값만 0으로 설정 (시작점은 최단거리가 0임)

- 거리 배열(dist) 내의 값들 중 최솟값을 골라준다. / 효과적으로 최솟값을 계속 찾아주기 위해서는 우선순위 큐를 이용해야 한다. 

function dijkstra(graph, source)
    set Q = Queue()

    for each vertex in graph
        set dist[v] = (1) # INF: 그래프의 모든 노드 v에 대하여 초기 dist[v]값은 아주 큰 값으로 초기화
        Q.push(v)

    set dist[source] = (2) # 0: source까지의 최단거리는 0 임

    while Q is not empty
        set u = vertex in Q with min dist
        Q.remove((3)) # u: dist값이 가장 작은 노드인 u를 큐에서 제거해야 하므로

        for each neighbor v of u
            set alt = dist[u] + length(u, v)
            if alt (4) dist[v]  # <: v까지의 새로운 거리 alt가 기존의 dist 값보다 작다면
                set dist[v] = (5) # alt: dist[v]값을 alt로 갱신해주어야 한다.

 

* 음수 가중치가 있는 그래프에서는 다익스트라가 올바르게 동작하지 않을 수 있다. 

-> dist 중 각 작은 값을 골랐을 때 그 값이 확실한 최단거리라는 보장이 되어야 하는데, 음수 가중치가 있으면 다시 골라졌던 정점에 도달하는 dist 값이 더 작아질 수도 있기 때문에 최단거리임을 보장할 수 없게 된다. 

import heapq

def dijkstra(graph, source):
    # 그래프의 노드 수만큼 큰 값을 저장하기 위한 변수
    INF = float('inf')
    
    # 시작점을 포함한 dist 배열 생성
    dist = {vertex: INF for vertex in graph}
    dist[source] = 0
    
    # 우선순위 큐 생성 (거리, 노드) 형식으로 저장
    Q = [(0, source)]  # (거리, 노드) 형식으로 저장
    
    while Q:
        # 가장 거리가 짧은 노드를 꺼냅니다.
        current_dist, u = heapq.heappop(Q)
        
        # 이미 처리된 노드라면 무시
        if current_dist > dist[u]:
            continue
        
        # 현재 노드와 연결된 모든 이웃 노드 탐색
        for neighbor, weight in graph[u].items():
            alt = current_dist + weight
            if alt < dist[neighbor]:
                dist[neighbor] = alt
                heapq.heappush(Q, (alt, neighbor))  # 새로운 경로가 발견되면 큐에 추가
    
    return dist

 

 

• BFS로 최단거리를 구할 수 있는 그래프라면 다익스트라로도 최단거리를 구할 수 있다. (가중치가 양수인 경우)
• 그래프 간선의 가중치가 서로 다른 경우 다익스트라를 이용하면 최단거리를 구할 수 있지만, BFS로는 최단거리를 구할 수 없다. 
• BFS의 시간복잡도 O(|V| + |E|), 다익스트라의 시간복잡도 O(|E|log|V|) or O(|V|^2)
  • BFS가 더 빠르므로 효율적임 
• for문을 사용하여 구현한 다익스트라의 시간복잡도 O(|N|^2)
  • N개의 정점에 대해 모두 시행해주면, 모든 지점에서 다른 지점까지의 최단거리를 구할 수 있다. 
  • 총 시간복잡도는 O(|N| * |N|^2) = O(|N|^3)
• 음수 가중치가 있는 그래프라면, 다익스트라를 통해 최단거리를 구할 수 없다. 
• 다익스트라는 무방향 그래프에서도 최단거리를 구할 수 있다. 
• 다익스트라를 한 번 이용하면, 모든 지점간의 최단거리가 아닌, 선택한 지점에서부터 모든 지점까지의 최단거리를 구할 수 있다.

 

• 우선순위 큐가 아닌 배열로 찾는 방법의 시간복잡도 O(|V|^2)