[파이썬] '최단경로' 개념 및 예제

그리디와 다이나믹 프로그래밍이 그대로 적용!

실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다, 단순히 최단 거리를 출력하는 문제 많이 출제됨!

 

 

최단거리 알고리즘 종류)
1. 다익스트라 최단거리
2. 플로이드 워셜          => 1,2가 많이 출제됨
3. 벨만 포드

 

1. 다익스트라 

- 그래프의 노드 중 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로 구함

- '음의 간선 없어야함'

- 그리디 알고리즘에 속함 ( 매번 '가장 비용 적은 노드' 선택하므로)

 

원리)

1. 출발 노드 설정

2. 최단 거리 테이블 초기화 (무한대로)

3. 방문 안 한 노드 중 최단거리 가장 짧은 노드 선택 ( 우선순위 큐를 사용하여 간단히 가능)

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

4. 3,4번 반복

 

1) 다익스트라 - 기본

# 간단한 다익스트라 알고리즘 

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)] # 각 노드마다 연결된 노드들의 정보 저장
visited = [False] * (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 get_smallest_node():
    min_value = INF
    idx = 0 # 최단 거리 가장 짧은 노드 (인덱스)
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i] # 최단 거리 가장 짧은 거 나올 떄 까지 min_value 계속 초기화
            idx = i # 최단 거리 가장 짧은 노드의 번호를 idx로 저장
    return idx

def dijkstra(start):

    # 시작 노드 
    distance[start]=0
    visited[start]=True 

    #시작 노드랑 연결된 노드들 최단거리 테이블 초기화
    for n in graph[start]:
        distance[n[0]] = n[1] 
    
    # 시작 노드 제외한 n-1개의 노드들 중
    for i in range(n-1):
        now = get_smallest_node() # 최단거리 가장 짧은 노드 now로 저장하고
        visited[now] = True       # 방문 True로 변경, (이게 현재 노드)

        # 현재 노드랑 연결된 노드들 중 (연결된 노드 : n) 
        for n in graph[now]:      
            cost = distance[now] + n[1] # cost : 현재 노드 거쳐서 n 까지 가는 거리
            if cost < distance[n[0]]:   # 지금까지 최단거리 테이블에 저장된 n까지의 거리가, 현재 노드 거쳐서 새로 계산한 cost 보다 크다면? 
                distance[n[0]] = cost   # 최단거리 테이블 값 거쳐가는 걸로 변경!!

# 다익스트라 수행
dijkstra(start)

# 노드마다의 최단거리 출력
for i in range(1, n+1):
    if distance[i] = INF: # 중간에 연결이 끊겨 도달 못한 노드
        print("INFINITY")
    else: 
        print(distance[i])

 

2) 다익스트라 - 우선순위 큐 사용

최단거리 테이블에서 '최단거리가 가장 짧은 노드를 선택'하는 과정을 우선순위 큐로 대체

 

위 간단한 다익스트라에서는 '최단거리가 가장 짧은 노드'를 찾기 위해서,

매번 최단 거리 테이블을 선형적으로(앞에서 부터 하나씩) 탐색해야 했었음.

-> 힙 자료구조를 이용해서 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하면 더 빨리 찾을 수 있다 ! 

 

=> 이제 방문을 체크하는 visited 와  최단거리가 가장 짧은 노드 찾아내는 get_smallest_node 함수가 필요없어짐 !!

 

파이썬에서 제공하는 heapq 모듈을 사용

heapq 는 리스트를 '최소 힙' 처럼 다룰 수 있다.

사용법)

import heapq
heap=[]
heapq.heappush( heap, 3 ) # heappush( 원소 추가 할 대상 리스트, 추가할 원소 )
heapq.heappop( heap )     # heappop( 원소 삭제할 대상 리스트 -> 가장 작은 원소 삭제 후 그 값 리턴)

 

# 개선된 다익스트라 알고리즘 -우선순위 큐 사용

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) ) # a 에서 b로 가는 비용이 c 


def dijkstra(start):

	#우선순위 큐
    q=[]
    heappush.( q , ( 0 , start) ) # q(큐)에 시작노드로 가는 최단거리 0으로 설정해서 삽입
   	distance[start] = 0 
    
    # q가 비어있지 않다면
    while q:
    	dist, now = heapq.heappop( q ) # q(큐)에서 최단 거리 가장 짧은 노드 정보 꺼내서 dist(거리), now(번호)로 저장
    	
        # 이미 최단 거리 테이블의 값이 더 작으면 무시 (= 이미 방문처리 된 것)
        if distance[now] < dist:
        	continue
        # 현재 노드와 연결된 다른 인접 노드들 확인
        for i in graph[now]:
        	cost = dist + i[1] # cost에 현재 노드를 거쳐 인접 노드 가는 거리 저장
            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])

 

'이것이 취업을 위한 코딩테스트다 python -나동빈' 책과 유튜브 강의를 보고 공부한 내용입니다.