탐색 알고리즘 정리 #2 - 다익스트라 알고리즘(Dijkstra algorithm)

하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. (shortest path from one node to every other node)

 

다익스트라의 개념은 출발점에서 이동 가능한 노드들을 찾고, 그 거리를 모두 기록합니다. 그리고 이 거리들 중 가장 짧은 것을 선택하고 이동하는것을 반복합니다. 마지막으로 한 노드까지의 경로를 리턴해주면 가장 짧은 경로를 알 수 있습니다.

 

이때 간선들은 모두 양의 간선들을 가져야 합니다. 하나의 정점에서 다른 모든 정점까지 각 정점별 최단 거리를 기록하는 배열이 있어야 합니다.

 

다익스트라 알고리즘은 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며, 이전보다 최단 경로값이라면 최소값을 계속 업데이트 합니다. (각 정점간의 거리들은 모두 무한대로 초기화 되어야 합니다.)

 

• 이때 우선순위 큐(Priority Queue)를 사용하여 처리하면 가장 짧은 노드에 대해 먼저 처리 할 수 있기때문에 효율적입니다. 즉, 거리가 먼 노드에 대한 계산을 생략할 수 있습니다.

 

백준의 1753 최단경로 문제를 통해 다익스트라 알고리즘을 우선순위큐를 사용해서 풀어보았습니다.

Python 구현 코드

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize

#우선순위큐를 사용한 다익스트라 알고리즘 구현
def dijkstra(start):
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        #한 노드에서 갈수있는 노드들의 정보(비용, 노드번호).
        weight, now = heapq.heappop(heap)
        #불필요한 계산 방지
        if(dist[now] < weight) : 
            continue
        #현재 노드에서 갈수있는 다음노드
        for w, nextNode in graph[now]:
            nextWeight = w + weight
            #현재노드 -> 다음노드까지의 비용이 다음노드의 최단경로값보다 작으면 갱신한다.
            if( nextWeight < dist[nextNode]):
                dist[nextNode] = nextWeight
                # 거리값이 갱신된(기존경로보다 짧은경로) 노드들만 다시 큐에 넣는다.
                heapq.heappush(heap, (nextWeight, nextNode))

if __name__ == "__main__" :
    V, E = map(int, input().split())
    start = int(input())
    graph = [[] for _ in range(V+1)]
    dist = [INF]*(V+1)

    for _ in range(E):
        u, v, w = map(int, input().split())
        graph[u].append((w,v))##가중치(비용)을 첫번째로 넣어야 우선순위큐에서 비교하는 key가 됩니다.

    dijkstra(start)

    for i in range(1,V+1):
        print("INF" if dist[i] == INF else dist[i])