파이썬 알고리즘 공부 - (4) 최단 경로 문제

최단 경로 문제

: 가장 짧은 경로를 찾는 알고리즘

: 노드, 간선으로 표현

 

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

: 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산

 

특징

- 매 상황에서 가장 비용이 적은 노드를 선택 -> 그리디 알고리즘으로 분류됨

- 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음

- 시간 복잡도 : O(노드개수)^2

 

<동작 과정>

 출발 노드 설정 -  최단 거리 테이블 초기화 - 방문하지 않은 노드 중 최단 거리가 짧은 노드 선택 (반복)

- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 (반복)

 

#다익스트라 알고리즘 구현
visited = [False]*(n+1) # 방문한 적 있는지 체크하는 리스트
distance = [INF] * (n+1) # 무한대로 초기화

def get_smallest_node():
	min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i range(1, n+1):
    	if distance[i] < min_value and not visited[i]:
        	min_value = distance[i]
            index = 1
    return index

def dijkstra(start):
	distance[start] = 0
    visited[start] = True
    for j in graph[start]:
    	distance[j[0]] = j[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):
	if distance[i] == INF:
    	print("inf")
    else:
    	print(distance[i])

 

노드의 개수가 많아지면 시간복잡도가 너무 높아짐

 

우선순위 큐 

: 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

 

힙(heap)

: 우선순위 큐를 구현하기 위해 사용하는 자료구조 

: 최소 힙, 최대 힙

: O(logN)

 

# 라이브러리 이용한 힙 구현
import heapq

def heapsort(iterable):
	h = []
    result = []
    for value in iterable:
    	heapq.heappush(h, value) # 최소 힙
        heapq.heappush(h, -value) # 최대 힙
    for i in range(len(h)):
    	result.append(heapq.heappop(h)) # 최소 힙
        result.append(-heapq.heappop(h)) # 최대 힙
    return result
    
    result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
    print(result)
    #최소 힙 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
    #최대 힙 : 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

이를 이용해서 다익스트라 알고리즘을 구현하면 최단 거리가 가장 짧은 노드를 선택하기 때문에 시간 복잡도를 낮출 수 있다

# 우선순위 큐를 활용한 다익스트라 구현
def dijkstra(start):
	q = []
    heapq.heappush(1, (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]))

 

📍플로이드 워셜 알고리즘

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

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

: -> 다이나믹 프로그래밍 유형

: O(N^3)

# 플로이드 워셜 알고리즘
for k in range(1, n+1):
	for a in range(1, n+1): # a : 출발노드, b : 도착노드
    	 for b in range(1, n+1):
         	graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])