[알고리즘] 이코테 - 최단경로

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.

최단경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 노드로 표현되고 지점간 연결된 도로는 그래프에서 간선으로 표현된다.

 

 

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

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

- 기본적으로 그리디 알고리즘이다 -> 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문

(출발 노드 설정 -> 최단 거리 테이블 초기화 -> 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택 -> 해당노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 -> 과정 반복)

- 즉, 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다.

 

 

동작원리: 1번노드를 출발노드라고 할 때, 초기상태에서는 다른 모든 노드로 가는 최단 거리를 무한으로 초기화(출발노드에서 출발노드로의 거리는 0으로 본다) -> 1번노드를 거쳐 다른 노드로 가는 비용 계산 -> 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 -> 최소 비용 리스트 업데이트 -> 반복 -

 

> 마지막 노드를 방문한 후 최단 거리 테이블이 의미하는 것은 1번 노드로부터 출발했을 때 각각의 노드로 도달하는 최단 경로를 의미한다. (한 단계 당 하나의 노드에 대한 최단 거리를 확실히 찾는 것과 마찬가지)

 

1) 간단한 다익스트라 알고리즘 (O(V^2): V는 간선 개수, 그리디 알고리즘 중 하나)

처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언

단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인한다(순차탐색)

 

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

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))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호 반환
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]
    for j 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):
 	if distance[i]==INF:
    	print("INFINITE")
    else:
    	print(distance[i])

 

O(V^2): 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색->현재노드와 연결된 노드를 매번 일일이 확인

노드 개수가 10000개를 넘어가면 사용이 어렵다.

 

2) 개선된 다익스트라 알고리즘 (O(ElogV): V는 노드 개수고 E는 간선 개수)

개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다. 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더운 빠르게 찾을 수 있다.

(힙 자료구조는 우선순위 큐를 구현하기 위해 사용하며, 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다)

 

그렇기 때문에 우선순위 큐를 이용해서 시작노드로부터 거리가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘을 작성. 최단거리를 저장하기 위한 1차원 리스트 + 현재 가장 가까운 노드를 저장하기 위한 우선순위 큐 사용.

 

 

튜플 (거리, 노드 번호)의 정보를 우선순위 큐에 넣는다. 파이썬의 heapq 라이브러리(항상 작은 값이 먼저 나옴, 단일데이터의 삽입삭제 연산 O(logN))는 원소로 튜플을 입력받으면 튜플의 첫번째 원소를 기준으로 우선순위 큐 구성->우선순위 큐에서 거리순으로 정렬

 

우선순위 큐에서 노드를 꺼낸 뒤에 해당 노드를 이미 처리한 적이 있다면 무시하고 처리하지 않은 노드에 대해 처리. 최소비용을 계산하고 더 짧은 경로를 찾은 경우 리스트 갱신 -> 더 짧은 경로를 찾은 노드 정보를 다시 우선순위 큐에 넣기 (더 짧게 갱신할 수 있는 방법이 없는 경우 우선순위 큐에 어떠한 원소도 들어가지 않게 됨)

 

마찬가지로 모든 단계를 거친 후에 최단 거리 테이블에 남아 있는 값이 각 노드로의 최단 거리이다.

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

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))

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]]:
            distance[i[0]]=cost
            heapq.heappush(q,(cost,i[0]))
dijkstra(start)
 for i in range(1,n+1):
 	if distance[i]==INF:
    	print("INFINITE")
    else:
    	print(distance[i])

 

앞의 코드와 비교하면 get_smallest_node()라는 함수를 작성할 필요 X. 최단 거리가 가장 짧은 노드를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체할 수 있기 때문

 

O(ElogV): 한번 처리된 노드는 더이상 처리되지 않는다. 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V이상의 횟수로는 반복되지 않는다. V번 반복할 때 각각 자신과 연결된 간선들은 모두 확인.

-> 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 총 최대간선 개수(E)만큼 연산이 수행됨.

 

플로이드 워셜 알고리즘(O(N^3) N은 노드의 개수, 다이나믹 프로그램 중 하나)

- 플로이드워셜 알고리즘: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용한다

 

단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.

 

모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 2차원 리스트에 최단 거리 정보를 저장.

2차원 리스트의 처리를 위해 N번의 단계에서 O(N^2)의 시간이 소요된다.

 

 

노드가 N개 일때, N번만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기때문에 다이나믹 프로그래밍이다.

알고리즘에서는 현재 확인하고 있는 노드를 제외하고 N-1개의 노드 중에서 서로 다른 노드 (A,B) 쌍을 선택하여 A->현재노드->B로 가는 비용을 확인한 뒤에 최단 거리를 갱신하는 것 (P(N-1,2)개의 쌍을 단계마다 반복해서 확인)

D(a,b)=min(D(a,b),D(a,k)+D(k,b))

 

3중반복문을 이용하여 위의 점화식에 따라 최단 거리 테이블 갱신

A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신

= 바로 이동하는 거리가 특정한 노드를 거쳐서 이동하는 거리보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신

 

INF=int(1e9)

n=int(input())
m=int(input())

graph=[[INF] *(n+1) for _ in range(n+1)]
#자기자신에서 자기자신은 0으로 초기화
for a in range(1,n+1):
	for b in range(1,n+1):
    	if a==b:
        	graph[a][b]=0
# 간선정보 입력
for _ in range(m):
	a,b,c=map(int,input().split())
    graph[a][b]=c
    
# 점화식 수행
for k in range(1,n+1):
	for a in range(1,n+1):
    	for b in range(1,n+1):
        	graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])
            
 # 수행결과 출력
for a in range(1,n+1):
	for b in range(1,n+1):
    	if graph[a][b]==INF:
        	print("INFINITY",end=" ")
        else:
        	print(graph[a][b],end=" ")
    print()