- 다익스트라 알고리즘은
한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘이다.- 플로이드-워셜 알고리즘은
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘이다.- 다익스트라 알고리즘은 그리디 알고리즘에 속하고 플로이드-워셜 알고리즘은 다이나믹 프로그래밍에 속한다.
- 다익스트라 알고리즘은 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 사용하지만 플로이드-워셜 알고리즘은 모든 지점에서 다른 모든 지점으로의 최단 거리를 저장하므로 2차원 리스트를 사용한다.
플로이드-워셜 알고리즘
- 각 단계마다 특정한 노드를 거쳐 가는 경우를 확인한다.
- 플로이드-워셜 알고리즘의 시간 복잡도는
O(N^3)이다.- 플로이드-워셜 알고리즘의 핵심 점화식은 다음과 같다.
a에서 b로 가는 최단거리와a에서 k를 거쳐 b로 가는 거리가 더 짧은지 확인하여 2차원 리스트에 저장하는 방법을 이용한다.
-
[step0] : 그래프 정보를 바탕으로 2차원 리스트를 초기화한다. 이 때, 그래프 정보를 바탕으로 추론할 수 없는 값은 무한으로 설정한다.
-
[step1] : 1번 노드를 거쳐 가는 경우를 고려한다.
-
[step2] : 2번 노드를 거쳐 가는 경우를 고려한다.
-
[step3] : 3번 노드를 거쳐 가는 경우를 고려한다.
-
[step4] : 4번 노드를 거쳐 가는 경우를 고려한다.
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
n = int(input()) # 노드의 개수
m = int(input()) # 간선의 개수
# 2차원 리스트를 만들고 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자기 자신에서 자기 자신으로 가는 비용은 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().strip().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):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if graph[a][b] == INF:
print("INFINITY", end = " ")
# 도달할 수 있는 경우, 거리를 출력
else:
print(graph[a][b], end = " ")
print()다익스트라 알고리즘
-
아래와 같은 그래프가 있을 때 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구해보자.
-
[step0] : 먼저 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발 노드가 선택된다.
-
[step1] : 출발 노드인 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 1번과 연결된 노드는 2, 3, 4번 노드가 존재한다. 2번 노드로 가는 비용은 2, 3번 노드로 가는 비용은 3, 4번 노드로 가는 비용은 1이 나온다.
-
[step2] : 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야한다. 2 ~ 4번 노드 중에서 최단 거리가 가장 짧은 노드는 4번이므로 4번 노드를 선택한다.
-
[step3] : 4번 노드와 연결된 노드는 3번과 5번 노드가 존재한다. 3번의 최단 거리를 갱신하면
1 + 3 = 4가 되고 5번 노드를 갱신하면1 + 1 = 2이 된다. 이 때, 갱신한 값을 보면 2번과 5번의 최단 거리 값이 같은 것을 알 수 있는데 일반적으로 최단 거리가 같은 경우 번호가 작은 노드를 먼저 선택한다.
-
[step4] : 5번 노드를 선택한다. 5번 노드와 연결된 3번, 6번 노드를 갱신한다.
-
[step5] : 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 3번 노드를 선택한다.
-
[step6] : 마지막으로 방문하지 않은 노드인 6번 노드를 선택한다.
- 다시 말해 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확정짓는 것으로 이해할 수 있다.
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().strip().split())
# 시작 노드 번호를 입력하기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for _ in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n+1)
# 최단 거리 테이블을 무한으로 초기화
distance = [INF] * (n+1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().strip().split())
# a번 노드에서 b번 노드로 가는 비용이 c라고 설정
graph[a].append((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[i] + 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])
- 위의 다익스트라 알고리즘의 시간 복잡도는
O(V^2)라고 헸다. 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 일반적으로 이 코드를 이용해 문제를 풀 수 있지만 노드의 개수가 10,000를 넘어가는 문제라면 개선된 다익스트라 알고리즘을 이용해야 한다.- 개선된 다익스트라 알고리즘을 이용하면
O(E log V)가 된다. 이 때, V는Vertex로 노드를 말하고 E는Edge로 간선을 말한다.- 개선된 다익스트라 알고리즘에서는 힙 자료구조를 이용한다.
-
[step0] : 1번 노드가 출발 노드인 경우라고 가정, 출발 노드를 제외한 모든 노드의 최단 거리를 무한으로 설정한다. 이후에 우선순위 큐에 1번 노드를 넣는다. 이 때, 1번 노드로 가는 거리는 자기 자신에서 자기 자신으로 가는 거리이기 때문에 0이다. 즉, (거리 : 0, 노드 : 1)의 정보를 가지는 객체를 우선순위 큐에 넣는다.
-
Python에서 heapq 라이브러리는 원소를 튜플로 입력받는 경우 디폴트로 첫 번째 원소를 기준으로 정렬이 수행된다는 것을 명심하자.
-
[step1] : 우선순위 큐에서 노드를 꺼낸 뒤에 해당 노드를 이미 처리한 적이 있다면 무시하고 넘어가면 되는 것이고 아직 처리하지 않은 노드에 대해서만 처리하면 된다.
-
[step2] : 최단 거리가 가장 짧은 노드는 4번 노드이다. 4번은 아직 방문하지 않은 노드이기 때문에 4번 노드를 처리하면 된다.
-
[step3] : 최단 거리가 가장 짧은 노드는 2번 노드이다. 2번은 아직 방문하지 않았으므로 2번 노드를 처리하면 된다.
-
[step4] : 최단 거리가 가장 짧은 노드는 5번 노드이다. 5번은 아직 방문하지 않았으므로 5번 노드를 처리하면 된다.
-
[step5] : 최단 거리가 가장 짧은 노드는 3번 노드이다. 3번은 아직 방문하지 않았으므로 3번 노드를 처리하면 된다.
-
[step6] : 우선순위 큐에서 원소를 꺼낸 결과
(거리 : 4, 노드 : 3)이 나오게 된다. 하지만 [step5]에서 3번 노드를 처리했기 때문에 무시한다.
-
[step7] : 최단 거리가 가장 짧은 노드는 6번 노드이다. 6번은 아직 방문하지 않았으므로 6번 노드를 처리하면 된다.
-
[step8] : 우선순위 큐에서 원소를 꺼낸 결과
(거리 : 5, 노드 : 3)이 나오게 된다. 하지만 [step5]에서 3번 노드를 처리했기 때문에 무시한다.
- 개선된 다익스트라 알고리즘 소스코드
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
V, E = map(int, input().strip().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for _ in range(V+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (V+1)
# 모든 간선 정보를 입력받기
for _ in range(E):
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
a, b, c = map(int, input().strip().split())
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드에서 시작 노드로 가는 비용은 0이다.
# 시작 노드로 가기 위한 최단 경로는 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]:
# graph의 정보 주의하자!
# graph[a] = (b, c) → a에서 b로 가는 비용이 c다.
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, V+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])📌다익스트라 최단 경로 알고리즘을 이용한 최단 경로 역추적
- 다익스트라 최단 경로 알고리즘 코드를 수정하면
경로도 역추적해서 찾을 수 있다.- 0으로 초기화한 부모 테이블을 선언한다.
- 최단 거리를 갱신할 때마다 어디서 왔는지 이전 노드를 기록한다. 예를 들어 B에서 C로 가는 경로를 갱신했다면
parent[C] = B로 저장한다. 이렇게 이동할 때마다 이전 노드를 저장하면 도착지에서 역으로 출발지를 추적할 수 있다.- 최단 경로를 역추적하기 위해 최종 목적지의 이전 노드부터 찾는 방법을 이용한다. 이후 반복해서 시작점까지 찾고 시작노드의 부모테이블 값이 0이면 멈춘다. 그래서 맨 처음에 부모 테이블을 0으로 초기화하는 것이다.
- 역추적이므로 거친 경로를 저장한 리스트를 거꾸로 뒤집어 출력하면 최단 경로가 출력되는 것을 확인할 수 있다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
parent = [0] * (n+1) # 부모 테이블의 모든 값을 0으로 초기화 후 선언
distance = [INF] * (n+1)
for _ in range(m):
# a → b로 이동하는 경우의 가중치는 c이다.
a, b, c = map(int, input().strip().split())
graph[a].append([b, c])
s, e = map(int, input().strip().split())
def dijkstra(start):
q = []
# q : (거리, 노드 번호)
heapq.heappush(q, [0, start])
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
# graph : graph[시작점] : [도착점, 가중치]
for next_node, next_dist in graph[now]:
cost = dist + next_dist
if distance[next_node] > cost:
distance[next_node] = cost
# 현재 노드에서 다음 노드로 이동
# 따라서 부모 테이블의 다음 노드 값을 현재 노드로 저장한다.
parent[next_node] = now
heapq.heappush(q, [cost, next_node])
return distance
res = dijkstra(s)
print(res[e])
# 거친 경로를 저장할 path 리스트
path = []
# 목적지 destination
destination = 0
while destination:
# 거친 경로에 목적지에서부터 역추적한 경로를 저장
path.append(destination)
destination = parent[destination]
print(len(path))
print(*path[::-1])