다익스트라(Dijkstra) 알고리즘

👇 관련 백준 문제
https://www.acmicpc.net/problem/1753

 

그래프에서 사용하는 최단경로 알고리즘
한 노드에서부터 도달할 수 있는 모든 노드까지의 최단경로를 찾는다.

힙을 사용해서 구현하는방법과 선형탐색으로 구현하는 방법이 있는데, 힙을 사용하는 편이 동작속도가 빠르므로 힙을 사용해서 구현하는 방법만 다루겠습니다.

 

❓ 힙을 사용하는게 빠른 이유 ❓
다익스트라 알고리즘에서는 매번 시작노드와의 거리가 가장 짧은 노드만을 선택해야 합니다. 그 이유는 최단거리를 갱신하는 알고리즘이기 때문에 현재 탐색한 경로 외에 더 짧은 미탐색 경로가 있을 경우 제대로 갱신되지 않을 수 있기 때문입니다.
따라서 선형탐색으로 가장 짧은 노드를 일일이 확인하는 것 보다 노드 길이를 기준으로 힙에 넣어서 최단거리를 바로바로 뽑아 탐색하는 것이 빠릅니다.

 

Pseudo Code

 

1. 각 노드간 연결된 가중치만 가지고 그래프 초기화, 최단거리를 저장하는 배열 초기화
2. 힙에 시작노드와 거리를 0으로 설정해서 삽입
3. 힙에서 pop해서 현재노드로 설정
4. 현재노드에 연결된 노드가 a 라고 했을 때 (시작노드 - a) 와 (시작노드 - 현재노드노드 - a) 의 거리를 비교해서 더 작은값으로 최단거리 배열에서 업데이트
5. 힙에 해당 노드 번호와 거리 삽입

 

위 알고리즘을 그림으로 표현하면 아래와 같습니다.

1.  

최단거리 정보는 start와 연결된 모든 노드들에 대한 최단거리를 저장하는 리스트 이며
현재 Start와 가장 가까운 거리에 있는 노드를 최소 힙에서 뽑아 연결된 노드들과 Start와의 거리를 비교하여 더 짧은 거리로 업데이트 및 힙에 삽입하여 연속적으로 탐색합니다.

 

Python Code

🔵 graph : 전체 그래프를 인접리스트로 구현
🔵 distance : start 노드로부터 연결된 각 노드간의 최단거리를 저장 (처음에는 inf (무한대) 의 거리로 초기화 한다.
🔵 q : 알고리즘에서 최단거리를 뽑기 위한 힙(우선순위 큐)으로 최소힙으로 구현

 

def dijkstra(start):
    distance = [inf] * (V + 1)      # start 노드로 부터 각 노드간 최단 거리 정보
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))   # 시작 노드 힙에 삽입 (시작 지점 이므로 거리는 0)
    while q:
        dist, now = heapq.heappop(q)        # 다음 노드 설정
        if distance[now] < dist:
            continue
        for dest in graph[now]:
            cost = dist + dest[0]           # 연결된 노드들과 시작노드간의 거리 계산
            if cost < distance[dest[1]]:    # 최단거리와 비교 및 업데이트
                distance[dest[1]] = cost
                heapq.heappush(q, (cost, dest[1]))      # 연속해서 최단거리 탐색할 수 있도록 힙에 삽입
    return distance     # 최단 거리 정보 반환
    ```