1. Dikstra algorithm
- 특정한 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 계산함
- 음의 간선이 없을 때 정상적으로 동작함
- 매 상황에서 가장 비용이 적은 노드를 선택하므로 그리디 알고리즘으로 분류됨
1.1 Dijkstra algorithm 동작 과정
- 출발 노드를 설정함
- 최단 거리 테이블을 초기화함
- 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택함
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신함
- 위 과정에서 3번과 4번을 반복함
1.2 Dijkstra algorithm 특징
- 그리디 알고리즘에 포함됨
- 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택하기 때문임
- 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음
- 한 단계당 하나의 노드에 대한 최단 거리를 확정짓는 것으로 이해할 수 있음
- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됨
- 최단 경로까지 구하려면 소스코드에 기능을 추가해야 함
1.3 Dijkstra algorithm 구현 코드
1.3.1 간단한 버전
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 찾기 위해서 1차원 테이블(distance)의 모든 원소를 순차 탐색함
- 전체 시간 복잡도가 O(V^2)
- 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하기 때문
- 일반적으로 전체 노드의 개수가 5,000개 이하라면 사용할 수 있음
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_shortest_node():
min_value = INF
index = 0
# 모든 노드에 대해
# 미방문이면서 최단거리에 있는 노드의 인덱스를 반환
for i in range(1,n+1):
if not visited[i] and min_value>distance[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 i in range(n-1):
# 최단거리에 있는 노드의 인덱스를 찾아냄
now = get_shortest_node()
visited[now] = True
# now노드의 인접노드들을 하나씩 확인하면서
# now노드를 거칠 때 거리가 더 짧아진다면 업데이트함
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("INFINITY")
else:
print(distance[i])
1.3.2 우선순위 큐를 사용해 실행시간을 단축한 버전
- 단계마다 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 찾기 위해 선형 탐색을 하는 것이 아니라, Heap을 사용함
- 현재 가장 가까운 노드를 저장하기 위해서 힙 자료구조를 추가적으로 사용한다는 점이 다름
- 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용함
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n,m = map(int, input().split())
start = int(input())
graph = [[]for _ in range(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 = []
# 힙에 거리와 노드번호를 튜플형태로 추가함
# 튜플의 첫 번째가 거리이므로 거리값을 기준으로 최소 힙이 만들어짐
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
# 기존의 거리보다 새로운 거리가 더 크다면
# 이미 최단 경로를 구한 적 있는 노드라는 뜻이므로 continue
if distance[now]<dist:
continue
# 인접한 노드들을 거쳐가는 경로 cost를 계산함
# cost가 기존 경로보다 짧다면 갱신하고
# 해당 노드를 정점에 추가함
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. Floyd-Warshall algorithm
- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산함
- 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행함
- 다만 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾는 과정이 불필요함
2.1 Floyd-Warshall algorithm의 특징
- 2차원 테이블에 최단 거리 정보를 저장함
- 다이나믹 프로그래밍 유형에 속함
- 각 단계마다 특정한 노드 k를 거쳐서 가는 경우를 확인함
- a→b로 가는 최단거리와 a→k로 가는 거리 중 더 짧은 것을 찾음
- 다음과 같은 점화식을 사용함
- 노드의 개수가 N개일 때 알고리즘상 N번의 단계를 수행함
- 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려함
- 따라서 총 시간 복잡도는 O(N^3)임
2.2 Floyd-Warshall algorithm 구현 코드
import sys
input = sys.stdin.readline
INF = int(1e9)
n,m = map(int,input().split())
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 i 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")
else:
print(graph[a][b],end=' ')
print()
<문제> 전보 - Dijkstra algorithm
①C한테 메시지를 받을 수 있는 도시의 개수와 ②메시지 전송에 걸리는 시간을 구해야 하는 문제이다.
다익스트라 함수를 실행해서 C에서 다른 도시까지의 최단 거리를 구해 distance에 저장한다.
①은 distance 리스트에 저장된 값이 INF가 아닌 도시의 개수를 세면 되고
②는 distance 리스트 값들 중 INF가 아니면서 가장 큰 값이 된다.
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
q = []
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if dist>distance[now]:
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]))
n,m,c = map(int,input().split())
graph = [[]*(n+1) for _ in range(n+1)]
distance = [INF]*(n+1)
for i in range(m):
x,y,z = map(int,input().split())
graph[x].append((y,z))
dijkstra(c)
cnt_city = 0
cnt_time = 0
for i in distance:
if i!=INF:
cnt_city+=1
cnt_time = max(cnt_time, i)
print(cnt_city-1, cnt_time)
<문제> 미래 도시 - Floyd-Warshall algorithm
k를 거쳐서 x까지 가는 데에 걸리는 최소시간을 구하는 문제이므로 플루이드 워셜 알고리즘을 사용하면 된다.
Dax = min(Dax, Dak+Dkx)
위 점화식을 사용해 모든 노드에서 다른 노드로 가는 최단 거리를 모두 구한 뒤에
D1k+Dkx를 출력해주면 된다.
import sys
input = sys.stdin.readline
INF = int(1e9)
n,m = map(int,input().split())
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
if i==j:
graph[i][j] = 0
for _ in range(m):
start,end = map(int,input().split())
graph[start][end] = 1
graph[end][start] = 1
x,k = map(int,input().split())
for c 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][c]+graph[c][b])
print(graph)
distance = graph[1][k]+graph[k][x]
if graph[k][x]==INF:
print(-1)
else:
print(distance)'Algorithm' 카테고리의 다른 글
| [다이나믹 프로그래밍] 피보나치 수열, 개미 전사, 1로 만들기, 효율적인 화폐 구성, 금광, 병사 배치하기 python (0) | 2023.09.28 |
|---|---|
| [구현] 상하좌우, 시각, 왕실의 나이트, 문자열 재정렬 python (0) | 2023.08.12 |
| [그리디 알고리즘] 1이 될 때까지 python (0) | 2023.08.11 |
