다익스트라(Dijkstra)

1. 다익스트라(Dijkstra)란?

• 다익스트라 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘
• 가중치가 있는 그래프에서 경로 비용을 최소화하는 데 사용
• 이 알고리즘은 우선순위 큐를 통해 효율적으로 작동하며, 우선적으로 최단 경로를 찾을 수 있는 정점을 탐색하는 방식으로 진행

---

2. 다익스트라의 동작 조건

• 비음수 가중치
  • 다익스트라 알고리즘은 모든 간선의 가중치가 음수가 아닐때 작동한다
• 연결된 그래프
  • 그래프 내의 모든 정점은 최소한 하나의 경로로 연결되어 있어야 하며 연결되지 않은 정점이 있는 경우, 해당 정점까지의 경로는 구할 수 없음
• 단일 출발점
  • 특정 하나의 시작점에서 다른 모든 정점으로 가는 경로를 찾는 데 적합, 다중 출발점이나 음수 가중치가 있는 경우 사용이 제한됨

---

3. 다익스트라 동작 방식

1. 초기화
   • 모든 정점에 대해 출발점으로부터의 거리를 무한대로 설정하고, 시작 정점에는 거리 0을 할당
2. 정점 선택
   • 방문하지 않은 정점 중에서 출발점과 가장 가까운 정점을 선택, 이 정점을 기준으로 주변 정점으로 가는 경로를 확인
3. 경로 업데이트
   • 선택된 정점의 인접한 정점으로의 거리를 계산한 후, 현재 저장된 거리보다 짧은 경우 경로를 업데이트
   • 이 과정을 통해 최단 경로를 갱신하고, 더 효율적인 경로를 발견하면 해당 경로를 저장
4. 반복
   • 모든 정점을 방문할 때까지 가장 가까운 정점을 선택하고, 경로를 갱신하는 과정을 반복
5. 최종 결과
   • 모든 정점을 탐색하면 출발점에서 각 정점까지의 최단 경로가 계산

---

4. 다익스트라 예제문제

백준 1916(최소 비용 구하기)

• 문제
  • N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.
• 입력
  • 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
    그리고 M+3째줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
• 출력
  • 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

입력
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

출력
4

# 다익스트라 알고리즘 활용
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9) #무한 설정

N = int(input()) # 도시의 수
M = int(input()) # 버스의 수

graph = [[] for _ in range(N+1)] # 노드 정보 담는 리스트
distance = [INF] * (N+1) # 각 도시까지의 최단 거리 저장 리스트

for _ in range(M):  
    u, v, w = map(int, input().split()) # 모든 간선 정보 입력
    graph[u].append((v, w))

start, end = map(int, input().split()) # 시작 노드와 끝 노드 입력받기

def dijkstra(start):
    q = []
    # 시작 노드 0으로 설정
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q: # q가 비어있지 않을 때
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내오기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

print(distance[end])

접근 방식

1. 초기 설정

• INF =int(1e9)
  • 무한대를 의미하는 값으로 설정
  • 다익스트라 알고리즘은 모든 노드의 초기 거리를 무한대(최대한 큰 수)로 설정한 후, 최단 경로를 갱신해 나가는 방식이므로, INF는 이 값을 대체
• graph = [[] for _ in range(N+1)]
  • *도시 간의 연결 관계(그래프)**를 저장할 리스트 제작
  • 도시 번호는 1부터 시작하므로 N+1로 리스트를 생성하고, 각 도시는 연결된 도시와 그 사이의 거리를 튜플로 저장
• distance = [INF]*(N+1)
  • 각 도시까지의 최단 거리를 저장할 리스트 제작
  • 처음에는 모든 도시까지의 거리를 무한대로 설정

2. 그래프 입력

• u, v, w = map(int, input().split())
  • 각 간선에 대해, u 도시에서 v 도시로 가는 거리가 w인 정보를 입력받음
• graph[u].append((v, w))
  • 인접 리스트 형식으로 그래프에 u 도시에서 v 도시로 가는 거리를 저장 (즉, 도시 u에 대한 리스트에 v와 w를 튜플로 추가)

3. 시작점과 종료점 입력

• start, end = map(int, input().split()) :
  • 시작 노드와 종료 노드를 입력받습니다. 이는 출발 도시와 도착 도시입니다.

4. 다익스트라 함수 정의

• def dijkstra(start):
  • 다익스트라 알고리즘을 정의하는 함수입니다. 출발점을 기준으로 최단 거리를 계산합니다.

5. 우선순위 큐 초기화 및 시작 노드 설정

• q = [] :
  • *우선순위 큐(최소 힙)**를 사용하기 위한 리스트를 초기화합니다.
• heapq.heappush(q, (0, start)) :
  • 시작 노드를 우선순위 큐에 거리 0과 함께 추가합니다. (현재 출발점의 거리는 0이므로 (0, start) 형태로 추가).
• distance[start] = 0 :
  • 시작 노드의 거리를 0으로 초기화합니다. 이로써 출발점에서 출발점까지의 거리는 0으로 설정됩니다.

6. 우선순위 큐를 사용한 최단 거리 계산

• while q: :
  • 우선순위 큐가 비어 있지 않은 동안 반복합니다.
• dist, now = heapq.heappop(q) :
  • 우선순위 큐에서 가장 최단 거리가 짧은 노드를 꺼냅니다. dist는 해당 노드까지의 거리, now는 해당 노드의 번호를 의미합니다.
• if distance[now] < dist: :
  • 이미 처리된 노드(즉, 이미 최단 경로가 구해진 노드)라면 무시합니다. 만약 현재의 dist 값보다 이미 저장된 distance[now] 값이 작다면 더 이상 탐색할 필요가 없기 때문입니다.

7. 인접한 노드 탐색 및 최단 거리 갱신

• for i in graph[now]: :
  • 현재 노드와 연결된 모든 인접한 노드를 확인합니다. i[0]은 인접한 노드 번호, i[1]은 그 노드까지의 거리입니다.
• cost = dist + i[1] :
  • 현재 노드를 거쳐서 인접한 노드로 가는 거리(dist + i[1])를 계산합니다.
• if cost < distance[i[0]]: :
  • 만약 이 새로운 경로가 더 짧다면(현재 저장된 거리보다 적다면), 해당 경로를 최단 거리로 갱신합니다.
• distance[i[0]] = cost :
  • 인접한 노드로 가는 최단 거리를 갱신합니다.
• heapq.heappush(q, (cost, i[0])) :
  • 갱신된 경로를 우선순위 큐에 다시 추가하여, 이 경로를 기반으로 다른 경로를 탐색하도록 합니다.

8. 결과 출력

• dijkstra(start) :
  • 주어진 시작점에서 다익스트라 알고리즘을 실행합니다.
• print(distance[end]) :
  • 최종적으로 시작점에서 종료점까지의 최단 거리를 출력합니다.

---

5. 다익스트라 장단점

• 장점
  1. 효율성
     • 우선순위 큐를 사용하여 O((V + E)logV)의 시간 복잡도를 가진다.(V는 정점의 수, E는 간선의 수)
     • 다익스트라 알고리즘은 대규모 그래프에서도 상대적으로 빠르게 최단 경로를 찾을 수 있다
  2. 안정성
     • 비음수 가중치가 있는 그래프에서 항상 최적의 해를 제공
     • 다른 경로 탐색 알고리즘보다 안정적으로 최단 경로를 보장하기 때문에 다양한 분야에서 사용
• 단점
  1. 음수 가중치 문제
     • 다익스트라 알고리즘은 음수 가중치를 처리할 수 없음
     • 음수 가중치가 있는 그래프에서는 벨만-포드 알고리즘과 같은 대체 알고리즘을 사용해야 함
  2. 모든 경로 탐색
     • 특정 두 정점간의 최단 경로만을 찾기 위한 경우에도 모든 정점을 탐색하는 과정을 거쳐야 하기 때문에, 특정 두 정점 간의 경로만 필요할 때는 비효율적

---

6. 결론

• 다익스트라 알고리즘은 비음수 가중치를 가진 그래프에서 단일 출발점에서 다른 모든 정점까지의 최단 경로를 효율적으로 찾는 알고리즘
• 음수 가중치를 다루지 못하며, 특정 경로만 필요할 때는 비효율적일 수 있다는 단점 존재
• 상황에 맞는 알고리즘 선택이 중요하며, 다익스트라는 비음수 가중치를 가진 단일 출발점 문제에서 좋은 성능을 발휘하는 알고리즘