[Python] 코딩테스트 유형 - 9. 최단 경로 알고리즘

최단경로(Shortest Path) 알고리즘

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

길 찾기 문제라고도 불림

• 애초에 Dynamic Programming 개념이 적용되어있음. 가장 적은 경로에서 축적해나가야 가장 최단 거리이기 때문

최단 경로의 여러 경우

• 한 지점에서 다른 특정 지점까지의 최단 경로
• 한 지점에서 다른 모든 지점까지의 최단 경로
• 모든 지점에서 다른 모든 지점까지의 최단 경로

Dijkstra Algorithm

: 다익스트라 알고리즘

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
• 음의 간선이 없을 때에만 정상적으로 동작. 다만 현실 세계에 반영하여 적합!
• 다익스트라 알고리즘은 그리디 알고리즘으로 분류됨.
  : 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문

알고리즘 동작 과정

1. 출발 노드를 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택함
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
5. 위의 3번과 4번을 반복함

다익스트라 알고리즘 성능

• 전체 시간 복잡도 : O(V^2)

• 일반적으로 코딩테스트 문제에서 최단경로 문제 출제시 1초라고 가정하면 노드 개수가 5,000개 이하라면 이 코드로 해결 가능

• 다만 노드의 개수가 10,000개를 넘어가는 경우 다른 알고리즘 설계 필요

Priority Queue

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

• 최소 힙, 최대 힙

• 다익스트라 최단경로 알고리즘을 포함해 다양한 알고리즘에서 사용됨

우선선위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

Python에서의 구현 방법

heap

import heapq

def heapsort(iterable):
	h = []
    result = []
    
    for value in iterable:
    heapq.heappush(h, value)
    
   	for i in range(len(h)):
    	result.append(heapq.heappop())
    return result

result = heapsort([1, 3, 5, 7, 9])
print(result)

💡 Python에서 최대 힙 사용하고 싶다면?

원소 부호를 바꿔서 넣고, 뺄 떄 다시 부호 바꿔주기

Python으로 구현한 Dijkstra

import heapq
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)]
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 = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
    	dist, now = heqpq.heqppop(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 graph:
	if distance[i] == INF:
    	print("INFINITY")
    else:
     	print(distance[i])

개선된 다익스트라 알고리즘 성능(ft. 우선순위 큐)

• 시간복잡도 : O(ElogV)
  • 단, 중복 간선을 포함하지 않는 경우

Floyd-Warshall Algorithm

• 모든 노드에서 다른 모든 노드까지의 최단 경로

• 노드의 개수가 적은 경우 유용. 노드/간선이 많은 경우 다익스트라가 나음

• O(N^3)

• 점화식
  

Python으로 플루이드 워셜 알고리즘 구현

# set infinite number
INF = int(1e9)

# get the number of nodes and edges
n = int(input())
m = int(input())

# create 2 dimensional list, set INF
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# set 0 for the distances from a node to the node itself
for a in range(1, n + 1):
  for b in range(1, n + 1):
    if a == b:
      graph[a][b] = 0

# get the input of edges information
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a][b] = c

# floyd-warshall algorithm
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])

# print the result
for a in range(1, n + 1):
  for b in range(1, n + 1):
    # if not reachable, print infinity
    if graph[a][b] == INF:
      print("Infinity", end = " ")
    # if reachable, print the distance
    else:
      print(graph[a][b], end = " ")
  print()