다익스트라 알고리즘

최단경로 알고리즘

가중 그래프에서, 하나의 노드로부터 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘

특징

- 매 방문시마다, 직전 최단 경로와 가중치의 합을 구해 해당 노드의 최단 경로를 갱신
- 현재 최단 경로 중 최소값은 "나의 현재 최단 경로가 보장되기 때문에, 해당 노드를 방문하는 것이 최단 경로임을 보장받음
- 음의 가중치가 없을 때 사용 가능

[ 활용 예시 ]
- GPS 시스템
- 인공위성 경로 시스템

---

원리

1. 각 정점까지의 최단 거리를 배열하는 dist[] 를 생성
   - 시작점은 0, 나머지 거리는 Inf에 가까운 값 배정
2. 노드와, 다른 노드까지의 최단거리를 한 쌍으로 우선순위 큐에 삽입
3. 반복문을 순회하며 큐에서 원소를 하나씩 꺼내 간선으로 연결된 다른 노드들을 검사
4. dist[] 를 참고하여 지금까지의 해당 노드에 대한 최단 경로보다 현재 검사 중인 정점까지의 최단거리 + 간선의 가중치가 더 작을 때, dist[]를 갱신하며 해당 정점의 이름과 거리를 우선 순위 큐에 삽입

---

최단 경로 검색방법

• 가중치가 없을 때 : BFS
• 가중치가 다르고, 음수 간선이 없을 때
  - 1차원 (시작점이 하나) : 다익스트라 (Dijikstra)
  - 2차원 (시작점이 여러개) : 플로이드-워셜 (Floyd-Warshall)
• 가중치가 다르고, 음수 간선이 있을 때 : 벨만-포드 (Bellman-Ford)
  
  

너비 우선 탐색(Breadth-First Search, BFS)과의 차이
- BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 알고리즘
- 좀 더 많은 정점을 지나가지만 가중치가 적은 경로가 있을 수 있음
- 가중치 그래프에서는 다익스트라 알고리즘이 가중치의 합이 작은 최단 경로를 찾는데 이용

• 다익스트라 알고리즘
  - 테이블 = 1차원 (시작점이 1개)
  - '거쳐가는 노드'를 기준으로 알고리즘 수행

• 플로이드-워셜 알고리즘
  - 테이블 = 2차원 (시작점이 n개)
  - '모든' 노드에서 모든 노드로의 최단 경로 탐색

---

예제

우선순위 큐

>>> input <<<

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 3
4 3 3
4 5 1
5 3 1
5 6 2

복잡도
- 최선 : O(E log E)
- 평균 : O(E log V)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값으로 10억

n,m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n+1)]
distance = [INF]*(n+1)

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

def dijkstra(start):
    q=[]
    heapq.heappush(q, (0, start))
    distance[start]=0

    while 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)


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

우선순위 큐가 불리할 때

E > V 일때, 우선순위 큐가 항상 빠름을 보장받을 수 없기 때문에 V를 기준으로 탐색하는 것이 더 빠르다.

복잡도 = O(V^2)

# 단계마다 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택하기 위해
# 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)한다.
 
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정
 
n,m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n+1)]
visited = [False]*(n+1)
distance = [INF]*(n+1)
 
for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))
 
def get_min_node():
    min_value=INF
    index = 0 
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index=i
    return index
 
def dijkstra(start):
    distance[start]=0
    visited[start]=True
    
    for j in graph[start]:
        distance[j[0]]=j[1]
        
    for i in range(n-1):
        now = get_min_node()
        visited[now] = True

        for j in graph[now]:
            cost = distance[now]+ j[1]
            
            if cost < distance[j[0]]:
                distance[j[0]]=cost
 
dijkstra(start)
 
#모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    if distance[i]==INF:
        print("INFINITY")
        
    else:
        print(distance[i])
    

>>> output <<<
0
2
3
1
2
4

---

예제 출처 , 출처2 , 출처3