최단 경로
특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘
가장 빠른 길 찾기
다익스트라 최단 경로 알고리즘
그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로 알고리즘
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 3 번과 4 번을 반복
각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장 & 계속해서 리스트(최단 거리 테이블) 갱신
간단한 다익스트라 알고리즘
💡 다익스트라 알고리즘 (순차탐색)
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)]
visited = [False] * (n + 1)
distance = [INF] * (n + 1) # 최단거리 테이블 초기화
for _ in range(m) :
a, b, c = map(int, input().split()) # 간선 정보
graph[a].append((b, c)) # a 노드에서 b 노드로 가는 비용 c
# 방문하지 않은 노드 중, 최단거리가 짧은 노드 번호 반환
def get_smallest_node() :
min_value = INF
index = 0 # 최단거리 노드 인덱스
for i in range(1, n + 1) :
if distance[i] < min_value and not visited[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]
# 시작노드 제외 전체 n - 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("INFINITY")
else :
print(distance[i])개선된 다익스트라 알고리즘
💡 다익스트라 알고리즘 (우선순위 큐)
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 = map(int, input().split()) # 간선 정보
graph[a].append((b, c)) # a 노드에서 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)
# 모든 노드로 가기위한 최단 거리 출력
for i in range(1, n + 1) :
if distance[i] == INF : # 도달할 수 없는 경우
print("INFINITY")
else :
print(distance[i])플로이드 워셜 알고리즘
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 알고리즘
💡 플로이드 워셜 알고리즘 (다이나믹 프로그래밍)
INF = int(1e9) # 10억 > 무한을 의미하는 값
n, m = map(int, input().split()) # 노드 개수, 간선 수
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 2 차원 리스트 모든 값 무한
# 자기 자신으로 가는 비용 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")
else :
print(graph[a][b], end = " ")
print()미래 도시
미래 도시
💡 플로이드 워셜 알고리즘
INF = int(1e9) # 10억 > 무한을 의미하는 값
n, m = map(int, input().split()) # 노드 개수, 간선 수
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 2 차원 리스트 모든 값 무한
# 자기 자신으로 가는 비용 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로 가는 비용 1
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
x, k = map(int, input().split()) # 거쳐 갈 노드 x, 목적지 노드 k
# 플로이드 워셜 알고리즘 수행
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])
distance = graph[1][k] + graph[k][x]
if distance >= INF :
print("-1")
else :
print(distance)전보
전보
💡 다익스트라 알고리즘 (우선순위 큐)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 10억 > 무한을 의미하는 값
n, m, start = map(int, input().split()) # 노드 개수, 간선 수, 시작 노드
graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1) # 최단 거리 테이블 무한으로 초기화
for _ in range(m) :
x, y, z = map(int, input().split())
graph[x].append((y, z))
def dijkstra(start) :
q = []
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)
count = 0 # 도달할 수 있는 노드 수
max_distance = 0 # 도달할 수 있는 노드 중 가장 멀리 있는 노드의 최단 거리
for d in distance :
if d != INF :
count += 1
max_distance = max(max_distance, d)
print(count - 1, max_distance)