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

하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 이때 음의 간선을 포함할 수 없다.

그래서 모든 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다.

 

구현할 때 dp를 활용할 수 있다.

dijkstra가 dp문제인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.'

기본적으로 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다.

 

# 구체적인 작동 과정))

1. 출발 노드를 설정한다.

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용을 갱신

5. 3번~4번을 반복한다.

 

최소 비용 배열(1차원 배열)로 최소 비용을 갱신하고 저장한다.

이 알고리즘은 최소 비용을 단순히 선형 탐색으로 찾도록 만들었다. 이럴 경우엔 시간 복잡도는 O(N^2)으로 형성된다.

 

최대한 빠르게 작동시켜야 하는 경우 힙 구조를 활용해 시간 복잡도 O(N * logN)을 만들 수 있다.

거리 값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소 힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 될 것이다.

파이썬의 경우 PriorityQueue나 heapq 라이브러리로 우선순위 큐, 최소 힙이 지원된다.

 

우선순위 큐에서 사용할 우선순위의 기준은 시작 노드로부터 가장 가까운 노드가 된다.

따라서 큐의 정렬은 최단 거리인 노드를 기준으로 최단 거리를 가지는 노드를 앞에 배치한다.

우선순위 큐를 사용하면 방문 여부를 기록할 배열은 없어도 된다. 우선순위 큐가 알아서 최단 거리의 노드를 앞으로 정렬하므로 기존 최단 거리보다 크다면 무시하면 그만이다.

기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣는다.

우선순위 큐에 삽입되는 형태는 <거리, 노드> 꼴이다.

 

참 : https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98