[알고리즘] 최단 경로 알고리즘

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

* 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로 계산

* 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류, 매 상황 가장 비용이 적은 노드를 선택하는 과정 반복.

 

동작 과정

① 출발 노드를 설정

② 최단 거리 테이블 초기화 (출발노드에서 출발노드까지 0, 출발노드에서 다른노드까지 무한)

③ 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택

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

⑤ 3번,4번 과정을 반복

 

특징

* 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택하는 과정 반복.

* 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지않음(한 단계당 하나의 노드에 대한 최단거리를 확실히 찾는 것으로 이해.)

* 다익스트라 알고리즘을 수행한 뒤 테이블에 각 노드까지 최단거리 정보가 저장 (완벽한 형태의 최단 경로를 구하려면 소스에 추가적인 기능을 더 넣어야함.)

 

 

성능분석

for문을 이용한 간단한 구현방법으로 한다면, 전체 시간 복잡도는 O(V^2)으로 노드 개수가 10,000개 넘으면 초과.

 

 

우선순위 큐(Priority Queue) , 힙(Heap)

* 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조(Python, C++, Java  등 표준라이브러리 형태로 지원)

* 힙(Heap) 자료구조 사용

① Heap 라이브러리 사용 예제 : 최소 힙

import heapq #파이썬에서 heap은 기본적으로 최소 힙으로 사용가능(우선순위가 낮은 값부터 꺼내짐)

#오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable: 
        heapq.heappush(h, value)
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result
    
result = heapsort([1,2,3,5,7,9,2,4,6,8,0])
print(result)
#[0,1,2,3,4,5,6,7,8,9]

 

② Heap 라이브러리 사용 예제 : 최소 힙

import heapq

#내림차순 힙 정렬(Heap Sort) : 최소 힙에 넣을때 부호반대, 꺼낼때도 부호 반대로 하면 최대힙으로 활용가능
def heapsort(iterable):
    h=[]
    result=[]
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value) #넣을때 부호반대
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h)) #꺼낼때 부호반대
    return result
    
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)
#[9,8,7,6,5,4,3,2,1,0]

 

다익스트라 알고리즘 heap 활용

* 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 Heap 자료구조를 이용.

* 다익스트라 기본 원리는 동일, 

  현재 가장 가까운 노드를 저장해놓기 위해 힙 자료구조를 추가적으로 이용(최단거리가 가장 짧은 노드 선택 시 최소 힙 사용)

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 (a:출발노드, b:도착노드, c:간선가중치)
    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)
#거리정보출력
print(distance)

 

입력값

그래프 변수 콘솔 출력

distance 출력값

 

=> 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV) 이다.

 

 

플로이드 워셜 알고리즘

* 모든 노드에서 다른 모든 노드까지의 최단 경로 계산

* 다익스트라 알고리즘과 마찬가지로 단계별 거쳐가는 노드를 기준으로 알고리즘을 수행

* 2차원 테이블에 최단 거리 정보를 저장

* 다이나믹 프로그래밍 유형에 속함

* 3중 반복문

 

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

#노드의 개수 및 간선의 개수 입력받기
n = int(intput())
m = int(input())

#2차원 리스트(그래프 표현)를 만들고, 무한으로 초기화
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라고 설정
    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()

 

=> 총 시간복잡도는 O(N^3)이다, 플로이드 워셜을 사용해야하는 알고리즘 문제는 노드가 500개 이하로 제한되는 경우가 많다.

 

 

 

 

 

이코테2021 강의를 바탕으로 정리한 내용이다