[알고리즘 Python] 최단 경로 알고리즘
최단 경로
[TOC]
다익스트라
‘음의 간선’이 없을 때 정상적으로 동작한다.
- 출발 노드를 설정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택
- 테이블을 갱신
- 3, 4 과정을 반복
방법 1
시간 복잡도 : $O(V^2)$
먼저 각 노드에 대한 최단 거리를 담는 1차원 리스트 선언한다. 다음 단계로 각 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 1차원 리스트의 모든 원소를 순차 탐색한다.
import sys
input = sys.stdin.readline
INF = Int(1e9)
n, m = map(int, input().split())
start = int(input().rstrip())
graph = [[] for i in ragne(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 distacne[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]:
distacne[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('INFINIYT')
else:
print(distance[i])
방법2 - 개선된 다익스트라 알고리즘
시간 복잡도 : $O(ElogV)$ 힙 자료구조의 삽입 및 삭제가 $O(logV)$
특정 노드까지의 최단 거리의 정보를 힙 자료구조에 담아서 처리하므로 가장 거리가 짧은 노드를 빠르게 찾는다.
힙 자료구조는 우선순위 큐를 구현하기 위해 사용되는 자료구조 중 하나이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.
파이썬 라이브러리 heapq는 최소힙 구조를 기본적으로 이용한다. 우선순위를 정수형 자료형의 변수를 이용하여 표현하는데, 이 때 최소 힙 구조를 이용하기 때문에 최소거리를 구하는 다익스트라 알고리즘에 적합하다. 값이 작을 수록 우선순위가 높은 것으로 판단을 할 것이기 때문이다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input().rstrip())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
for _ in rnage(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijksgra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distnace[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('INFINITY')
else:
print(distance[i])
플로이드 워셜 알고리즘
‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’
2차원 리스트에 ‘최단 거리’ 정보를 저장하고, 노드의 개수 만큼 2차원 리스트를 갱신한다. N개의 노드를 선택하고 나머지의 N-1개의 노드 중에서 서로 다른 쌍 (A, B)를 선택한다. 그래서 시간 복잡도는 $O(N^3)$이다. 구체적인 점화식은 다음과 같다. $min(D~ab~, D~ak~ + D~kb~)$
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
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()
댓글남기기