최단 경로 알고리즘 : 다익스트라

 최단 경로 알고리즘은 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다.

 

다익스트라 최단 경로 알고리즘

---

 

개념

 - 그래프에 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다.

- '음의 간선'이 없을 때 사용할 수 있다.

- GPS 소프트웨어 기본 알고리즘으로 채택되곤 한다.

- 그리디 알고리즘으로 분류된다. (매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문)

- heapq(우선순위 큐) 사용 시, 시간 복잡도 : O(ElogV) (V : 노드 개수, E : 간선 개수) 

  최단 거리가 가장 짧은 노드를 순차 탐색이 아니라 힙 자료구조를 사용함으로써 시간복잡도를 줄인다. 힙 자료구조를 이용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.

 

 

원리

한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는다.

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

2) 최단 거리 테이블을 초기화한다.

3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.

4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

   (각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다.)

5) 위 과정에서 3), 4) 번을 반복한다.

 

구현

import heapq # 우선순위 큐
import sys
input = sys.stdin.readline 
INF = int(1e9)

n, m = map(int, input().split()) # 노드 개수, 간선 개수
start = int(input()) # 시작 노드 번호

# 그래프 생성
graph = [[] for _ in range(n + 1)]

# 최단 거리 테이블 무한으로 초기화
distance = [INF] * (n + 1) 

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c)) # a번 노드에서 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("INFINITY")
    else:
        print(distance[i])
        
'''
# 입력
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

# 출력 
0
2
3
1
2
4
'''