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

들어가며: 최단경로 알고리즘, 다익스트라 란?

다익스트라 알고리즘 동작 과정

heapq 란?

heapq 을 사용한 다익스트라 알고리즘 구현

관련 문제

 

---

들어가며: 최단경로 알고리즘, 다익스트라 이란?

 

 

최단 경로 알고리즘은 현재 위치에서 가고자 하는 위치까지 가장 짧은 경로를 찾는 알고리즘을 의미

 

다익스트라 알고리즘은 최단 경로 알고리즘 종류 중 1가지. (다익스트라, BFS, 벨만-포드, 플로이드, a* ...)

다익스트라 알고리즘은 음의 간선을 표현할 수 없음. (음의 간선 표현은 벨만포드 알고리즘을 활용)

다익스트라 알고리즘은 그리디 알고리즘으로 분류

매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

 

 

해당 포스팅은 이것이 코딩 테스트다 를 참고하여 작성하였습니다.

 

---

다익스트라 알고리즘 동작 과정

1. 출발 노드를 설정

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

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

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

5. 위 과정에서 3번과 4번을 반복

 

기본적인 다익스트라 알고리즘으로 구현하게 되면 최단 거리가 짧은 노드를 선택할 때마다 매번 선형 탐색을 해야함.

따라서, 전체 시간 복잡도는 O(V^2) [V: 노드, E: 간선]

전체 노드의 개수가 5,000개 이하라면 이 코드로 문제를 해결할 수 있음.

하지만, 노드의 개수가 10,000개가 넘어가는 문제라면 시간 초과가 남.

 

하지만, heapq 자료구조를 사용하면 시간 복잡도를 줄일 수 있음.

 

 

---

heapq 란?

내장 모듈로 이진트리(Binary Tree)를 기반으로 한 최소 힙(min heap) 정렬 트리를 제공

최대 힙을 사용하고 싶으면 -를 붙혀 값을 넣었다가 뺄 때 -를 붙혀 사용

 

import heapq

heap=[]
heapq.heappush(heap,4)
heapq.heappush(heap,1)
heapq.heappush(heap,8)
heapq.heappush(heap,7)
heapq.heappush(heap,5)

print(heap)
# 출력: [1,4,5,7,8]

a=heapq.heappop(heap)
print(a)
# 출력: 1

a=heapq.heappop(heap)
print(a)
# 출력: 4

 

 

---

heapq 을 사용한 다익스트라 알고리즘 구현

 

import heapq
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

#노드의 개수, 간선의 개수를 입력받기
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())
    #a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b,c))

def dijkstra(start):
    q=[]
    #시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    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]]:
                heapq.heappush(q,(cost,i[0]))
                dist[i[0]]=cost

#다익스트라 알고리즘을 수행
dijkstra(start)

#모든 노드로 가기 위한 최단 거리를 출력
for i in range(1,n+1):
    #도달할 수 없는 경우, 무한이라고 출력
    if distance[i]==INF:
        print("INFINITY")
    else:
        print(distance[i])