[Algorithm] Dijkstra(다익스트라) 이론 + 예제

❗Dijkstra(다익스트라)란?

다익스트라(Dijkstra) 알고리즘은 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이며 가중치가 있는 양의 가중치 그래프에 사용된다. 

 

 

❗다익스트라 알고리즘의 원리

1. 초기 설정:
   • 시작 노드에서 모든 노드까지의 최단 거리를 저장하는 배열(distance)을 생성하고 모든 거리를 무한대로 초기화
   • 시작 노드의 거리는 0으로 설정
2. 우선순위 큐 사용:
   • 시작 노드부터 출발하여 우선순위 큐(또는 최소 힙)에 현재 거리가 가장 짧은 노드를 선택하여 탐색을 진행
   • 매번 가장 짧은 거리를 가진 노드를 선택해 그 노드의 인접한 노드들을 확인
3. 최단 거리 갱신:
   • 현재 노드에서 인접 노드로 가는 거리가 기존에 기록된 거리보다 짧으면 distance 배열을 갱신
   • 갱신된 정보를 큐에 추가하여 다시 탐색할 수 있도록 함
4. 반복 종료:
   • 큐가 빌 때까지 반복하여 모든 노드에 대한 최단 거리를 구함

 

 

❗예시 코드

def dijkstra(start):
    dist = [float('inf') for _ in range(N+1)]
    pq = []

    dist[start] = 0
    pq.append((0, start))


    while pq:
        cur_dist, cur = heappop(pq)    # 현재 거리, 현재 노드

        if dist[cur] < cur_dist:   # 이미 처리된 노드는 패스
            continue

		
        # 인접 노드의 거리 갱신
        for next, weight in graph[cur]:
            new_dist = dist[cur] + weight

            if dist[next] > new_dist:
                dist[next] = new_dist
                heappush(pq, (new_dist, next))

    return dist

 

 

❗참고문제

https://www.acmicpc.net/problem/1916

https://www.acmicpc.net/problem/1753

https://www.acmicpc.net/problem/1238