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

https://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 예스24

 

---

다익스트라 알고리즘

음의 간선이 없을 때 사용된다.

 

최단 거리를 모두 무한으로 초기화한다.

-> 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 찾는다

-> 그 노드를 통해서 최단 거리를 줄일 수 있으면 갱신

모든 노드 반복

 

짧은 노드부터 찾는 이유: 최단 거리가 완전히 선택된 노드이므로, 최단 거리가 더이상 감소하지 않는다.

 

 

필요

시작 노드, 그래프, 방문 리스트, 시작 노드의 최단 거리를 저장하는 1차원 리스트

 

import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드 수, 간선 수 입력
n, m = map(int, input().split())

# 시작 노드
start = int(input())

# 연결 노드 정보
graph = [[] for _ in range(n+1)]
# 방문 리스트
visited = [False] * (n+1)
# 최단 거리를 위한 1차원 리스트
distance = [INF] * (n+1)

# 그래프에 연결 정보 추가 
for _ in range(m):
    # 노드, 노드, cost
    a, b, c = map(int, input().split())
    graph[a].append((b,c)) # 노드와 거리(방향 그래프이면)
    # 무방향 그래프면 graph[b].append((a,c)) 도 추가

 

방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 찾는 함수

# 최단 거리가 제일 짧은 노드 반환
def get_smallest_node():
    mini = INF
    idx = 0
    for i in range(1, n+1):
        if distance[i] < mini and visited[i]==False:
            mini = distance[i]
            idx = i
    return idx

 

다익스트라 알고리즘으로 최단 거리를 찾는 함수

def dijkstra(start):
    distance[start] = 0
    visited[start] = True
    
    for i in graph[start]:
        distance[i[0]] = i[1]
        
    # 시작 노드 제외 n-1개 노드 반복
    for _ in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        for i in graph[now]: # i[0]은 노드, i[1]은 거리
            cost = distance[now] + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost

 

호출

dijkstra(start)

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

 

시간 복잡도 O(V^2)

V: 노드의 수

10000개를 넘어가면 해결하기 어렵다

---

개선된 다익스트라 알고리즘(힙과 함께)

 

힙

2024.02.05 - [Python] - [Python] 힙

[Python] 힙

최소힙을 사용한다(heappop을 했을 때 작은 것이 먼저 나온다)

최단 거리가 가장 짧은 노드를 찾기 위해 우선순위 큐처럼 동작하게 한다.

 

 

필요

시작 노드, 그래프, 시작 노드의 최단 거리를 저장하는 1차원 리스트, 힙 정렬을 위한 리스트

 

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

# 노드 수, 간선 수 입력
n, m = map(int, input().split())

# 시작 노드
start = int(input())

# 연결 노드 정보
graph = [[] for _ in range(n+1)]
# 최단 거리를 위한 1차원 리스트
distance = [INF] * (n+1)

 

우선순위를 위해

(거리, 노드) 로 저장한다

for _ in range(m):
    # 노드, 노드, cost
    a, b, c = map(int, input().split())
    graph[a].append((c,b)) # 거리와 노드(방향 그래프이면) -> 거리를 우선으로 봐야 하니까
    # 무방향 그래프면 graph[b].append((c,a)) 도 추가

 

최소힙을 이용한 다익스트라

while q:
        dist, now = heapq.heappop(q) # 제일 작은 거 빼
        
        if distance[now] < dist: # 이미 처리 되었으면
            continue
        
        for i in graph[now]: # i[0]은 거리, i[1]은 노드
            cost = dist + i[0]
            if cost < distance[i[1]]:
                distance[i[1]] = cost
                heapq.heappush(q, (distance[i[1]],i[1]))

 

호출

dijkstra(start)

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

 

 

시간 복잡도 O(ElogV)

V: 노드의 수

E: 간선의 수