on
최단경로 알고리즘
최단경로 알고리즘
최단경로 알고리즘이란 ?
말그대로 가장 짧은 경로를 찾는 알고리즘이다.(길 찾기 문제라고도 불림)
최단경로 알고리즘의 종류는 많으나 상황에 맞는 효율적인 알고리즘은 이미 정립되어있다.
(한 지점~ 다른 특정 지점까지의 최단경로를 구할때, 모든 지점에서 다른 모든 지점의 최단경로를 모두 구할때 등)
최단경로 문제는 그래프를 이용해 표현하며 각 지점은 그래프에서 '노드'로 표현되고 지점간 연결된 도로는 그래프의 '간선'이 된다.
(ps에서는 최단경로를 모두 출력하기보다 단순히 최단 거리를 출력하도록 요구하는게 많다.)
가장 많이 쓰이는 최단거리 알고리즘은 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘이다.
다익스트라 최단 경로 알고리즘(Dijkstra)
다익스트라 최단 경로 알고리즘은 그래프안의 여러개의 노드 중 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해야 할때 활용하기 좋다.
Dij는 '음의 간선' 이 없어야 정상적으로 동작한다.(실제 길이 존재해야하므로 GPS에서 활용됨)
기본적으로 그리디 알고리즘으로 분류 되는데 매번 '가장 적은 비용의 노드'를 선택해 다음의 과정을 반복하기 때문이다.
1. 출발 노드를 설정.
2. 최단 거리 테이블을 초기화
3. 방문 하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리테이블을 갱신
5. 3,4를 반복
Dij는 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단거리'를 1차원 리스트에 저장하며 갱신해나간다는 특징이 있다.
Dij의 구현방법은 두가지이다.
1. 구현하기 쉽지만 느리게 동작
2. 구현하기 까다롭지만 빠르게 동작
ps에선 당연히 2번 방법을 완벽히 숙지해야한다.
간단하게 구현한 다익스트라 알고리즘
V를 노선이라고 할때 간단하게 Dij를 구현하면 시간복잡도는 O(V^2)이다.(직관적이고 쉽게 이해됨)
처음에 각 노드에 대한 최단거리를 담는 1차원 리스트를 선언
단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드'를 선택하기 위해 매 단계마다 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 ) # 방문 여부를 체크하기위한 리스트
distance =[ INF ]*( n + 1 ) # 최단거리 테이블의 처음값은 무한으로 설정
# 모든 간선의 정보 입력 받기
for _ in range ( m ):
a , b , c = map ( int , input (). split ()) # a에서 b로가는 비용이 c
graph [ a ]. append (( b , c ))
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호 반환 하는 함수
def get_smallest_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 ]
# 시작노드를 제외한 전체 n-1개의 노드에 대해 반복
for i in range ( n - 1 ):
# 현재 최단거리가 가장 짧은 노드를 꺼내, 방문 처리
now = get_smallest_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 ):
# 노달할수 없는 경우 무한(INFINITY)라고 출력
if distance [ i ]== INF :
print ( "INFINITY" )
# 도달할 수 있는 경우 거리를 출력
else :
print ( distance [ i ])
시간복잡도가 O(V^2)인 이유는 O(V)번 최단 거리가 가장 짧은 노드를 선형 탐색해야하기 때문이다.
따라서 노드의 개수가 10000개가 넘어가면 이 코드로는 문제를 해결하기 어려우므로 개선된 다익스트라 알고리즘을 써야한다.
개선된 다익스트라 알고리즘
이 방법을 사용하면 시간복잡도 O(ElogV)를 보장 받을 수 있다.(V=노드의 개수, E는 간선의 개수)
앞서 간단한 다익스트라 알고리즘은 매번 최단거리테이블을 선형적으로 탐색함으로써 O(V)의 시간이 걸렸다.
하지만 힙(Heap)자료구조를 사용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 더욱빠르게 탐색을 할 수있다. 이 과정에서 선형이 아닌 로그의 시간이 걸린다.
힙이란?
힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 사용되는 자료구조 중 하나이다. 우선순위 큐 는 들어온 순서에 따라 삭제를 정하는 스택(Stack)이나 큐(Queue)와 달리 우선순위가 가장 높은 데이터를 먼저 삭제한 다는 특징이 있다.
우선순위 큐에는 데이터를 (가치,물건)으로 묶어서 넣을 수 있다. 이후 데이터를 꺼내면 가치의 순서대로 물건이 나오게 된다.
tip. 우선순위 큐의 구현에는 내부적으로 최소 힙, 최대 힙을 이용하는데 최소 힙은 가치가 낮은것부터, 최대 힙은 가치가 높은 것 부터 삭제한다. 파이썬 라이브러리의 힙의 기본값은 최소 힙으로 설정되어있는데 다익스트라 최단 경로 알고리즘은 비용이 적은 노드 부터 우선 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.
구현방식 삽입시간 삭제시간 리스트 O(1) O(N) 힙 O(logN) O(logN)
데이터의 개수가 N개일때, 힙 자료구조에 데이터를 전부 넣고 다시 꺼내는 경우의 시간복잡도는
삽입시 O(NlogN) 삭제시 O(NlogN)이므로 전체 연산 횟수는 대략 2Nlog₂N이지만 빅오표기법으로 O(NlogN)이 된다.
실제 로 Heap을 사용하야 구현할 시 간단한 다익스트라 알고리즘과 달리 get_samllest_node를 사용할 필요가 없다.
우선순위 큐가 최소 거리를 선택해 주기 때문이다.
구현 :
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 ()) # a에서 b로가는 비용이 c
graph [ a ]. append (( b , c ))
def dijkstra ( start ):
q =[]
# 시작 노드, 자기자신으로 가는 최단거리는 0, 큐에 삽입
heapq . heappush ( q ,( 0 , start ))
distance [ start ]= 0
while q : # 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 ]]: # now 노드를 거쳐가는 것이 최단거리일 경우
distance [ i [ 0 ]]= cost
heapq . heappush ( q ,( cost , i [ 0 ]))
dijkstra ( start ) # 다익스트라 알고리즘 수행
#모든 노드로 가기위한 최단거리를 출력
for i in range ( 1 , n + 1 ):
# 노달할수 없는 경우 무한(INFINITY)라고 출력
if distance [ i ]== INF :
print ( "INFINITY" )
# 도달할 수 있는 경우 거리를 출력
else :
print ( distance [ i ])
이 개선된 다익스트라 알고리즘의 시간복잡도는 O(ElogV)로 기존의 방식보다 훨씬 빠르다.
플로이드 워셜 알고리즘
다익스트라 알고리즘의 경우 '한 지점에서 다른 특정 지점까지의 최단 경로'를 구해야 하는 경우'에 사용할 수 있다.
하지만 '모든 지점에서 다른 모든 지점까지의 최단경로'를 구해야 할 경우 플로이드 워셜 알고리즘을 사용해야한다.
소스코드가 짧아 구현이 어렵지는 않으나 핵심아이디어를 이해하는 것이 중요하다.
다익스트라 처럼 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행하나 매번 방문하지 않은 노드 중 최단거리 갖는 노드를 찾을 필요가 없다. 노드의 개수가 N개 일때 N번단계를 수행하며 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 즉 총 시간 복잡도는 O(N^3)이다.
다익스트라는 출발노드가 1개이므로 1차원 리스트를 사용했지만 플로이드 워셜은 2차원 리스트에 '최단거리'정보를 담아야 한다.[O(N^2)]. 또한 N개의 노드를 N번 단계 반복을 하며 점화식 처럼 2차원 리스트를 갱신하므로 다이나믹 프로그래밍의 일종으로 볼 수 있다.
각 단계에서 해당 노드를 거쳐가는 경우를 고려한다. (1번 노드에 대해 확인할 때 1번 노드를 중간에 거쳐가는 모든 경우 고려) 따라서 현재 노드를 제외한 (n-1)개의 노드 중 서로다른 노드 (A,B)쌍을 선택한 이후, A->k번노드->B로 가는 비용을 확인해 최단거리를 갱신한다.
점화식으로 표현 : D ab =min(D ab ,D ak +D kb )
구현 :
INF = int ( 1e9 ) # 무한을 의미
n , m = map ( int , input (). split ()) # 노드,간선
graph =[[ INF ]*( n + 1 ) for _ in range ( n + 1 )] # 2차원 리스트를 만들고, 초기값은 모두 무한으로 설정
for i in range ( 1 , n + 1 ):
for j in range ( 1 , n + 1 ):
if i == j :
graph [ i ][ j ]= 0
# 모든 간선의 정보 입력 받아 그 값으로 초기화
for _ in range ( m ):
a , b , c = map ( int , input (). split ()) # a에서 b로가는 비용이 c
graph [ a ][ b ]= c
# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range ( 1 , n + 1 ):
for i in range ( 1 , n + 1 ):
for j in range ( 1 , n + 1 ):
graph [ i ][ j ]= min ( graph [ i ][ j ], graph [ i ][ k ]+ graph [ k ][ j ])
# 수행된 결과를 출력
for i in range ( 1 , n + 1 ):
for j in range ( 1 , n + 1 ):
if graph [ i ][ j ]== INF : # 노달할수 없는 경우 무한(INFINITY)라고 출력
print ( "INFINITY" , end = ' ' )
else : # 도달할 수 있는 경우 거리를 출력
print ( graph [ i ][ j ], end = ' ' )
print ()
from http://20210916start.tistory.com/54 by ccl(A) rewrite - 2021-09-23 03:00:49