2024. 9. 7. 16:28ㆍ알고리즘
♠ 기본 내용
그래프는 정점(노드)와 간선으로 이루어져 있는데 간단한 그래프 형식이라면 노드와 간선의 존재만 고려하면 된다. 하지만 여기에 '가중치'라는 개념이 추가될 때가 있다. a 노드와 b 노드를 이어주는 x라는 간선이 있을 때, 이 간선이 weight라는 가중치를 가질 수 있는 것이다. 이 경우 a -> b로 갈 때 weight 만큼의 비용이 필요하게 된다.
예를 들어 한 도시에서 다른 도시로 가는 최단 거리를 구한다고 해보자. 이때 각 도시는 노드, 각 도시를 잇는 경로는 간선이 된다. 또한 한 도시와 다른 도시를 잇는 경로의 거리는 가중치가 된다. A 도시에서 B 도시로 갈 때, 다양한 경로를 이용하여 이동할 수 있겠지만 그 중에서도 가중치가 가장 작은, 즉 최단 거리를 찾는 문제에서 데이크스트라 알고리즘과 플로이드-워셜 알고리즘을 사용할 수 있다.
♠ 데이크스트라의 개념
그래프에서 노드 간의 최단 경로를 찾는 알고리즘 중 하나로, 컴퓨터 과학자 에츠허르 데이크스트라가 고안했다.
위의 그래프에서 1번 노드와 5번 노드의 최단 경로를 찾는다고 해보자. 처음에는 시작 노드를 제외한 모든 노드로의 거리를 무한대로 설정한다. 그리고 인접한 노드들을 방문하면서 최소 비용을 갱신해나간다.
이렇게 1번 노드에서 출발하여 5번 노드로의 최단 경로를 찾을 수 있다. (1 -> 3 -> 6 -> 5)
♠ 데이크스트라의 특징
- 출발 노드로부터 가장 거리가 짧은 노드를 더 빠르게 찾기 위해 heap을 사용한다.
- 데이크스트라의 시간 복잡도는 최대 간선의 개수를 E, 노드의 개수를 V라고 했을 때 O(ElogV)이다.
♠ 데이크스트라 기본 코드
def dijkstra(graph, start):
distances = [1e9] * (n + 1)
distances[start] = 0
que = []
heapq.heappush(que, [0, start]) # que에다 첫 번째 요소 집어넣기
while que:
dist, end = heapq.heappop(que)
# 원래의 거리보다 새로운 거리가 더 길면 갱신하지 않는다.
if dist > distances[end]:
continue
# 원래의 거리보다 새로운 거리가 짧으면 갱신한다.
for next_node, next_dist in graph[end]:
distance = dist + next_dist
if distance < distances[next_node]:
distances[next_node] = distance
heapq.heappush(que, [distance, next_node])
return distances
♠ 데이크스트라 알고리즘 문제 풀기
백준 알고리즘 11404번: https://www.acmicpc.net/problem/11404
import sys
import heapq
input = lambda: sys.stdin.readline().strip()
n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(m):
start, end, weight = map(int, input().split())
graph[start].append([end, weight])
print(graph)
def solution(graph, start):
distances = [1e9] * (n + 1)
distances[start] = 0
que = []
heapq.heappush(que, [0, start]) # que에다 첫 번째 요소 집어넣기
while que:
dist, end = heapq.heappop(que)
if dist > distances[end]:
continue
for next_node, next_dist in graph[end]:
distance = dist + next_dist
if distance < distances[next_node]:
distances[next_node] = distance
heapq.heappush(que, [distance, next_node])
return distances
for i in range(1, n + 1):
ans = solution(graph, i)
ans = [0 if x == 1e9 else x for x in ans]
print(*ans[1:])
그래프(노드와 간선의 연결)
1번 노드로부터 각 노드까지의 최단 거리 탐색
| distances | heap |
| [1000000000.0, 0, 2, 3, 1, 10] | [[1, 4], [3, 3], [2, 2], [10, 5]] |
| [1000000000.0, 0, 2, 3, 1, 4] | [[2, 2], [3, 3], [10, 5], [4, 5]] |
| [1000000000.0, 0, 2, 3, 1, 4] | [[3, 3], [4, 5], [10, 5]] |
| [1000000000.0, 0, 2, 3, 1, 4] | [[4, 5], [10, 5]] |
| [1000000000.0, 0, 2, 3, 1, 4] | [[10, 5]] |
♠ 플로이드-워셜의 개념
데이크스트라가 한 지점에서 다른 지점까지의 최단 경로를 구하는 알고리즘이라면 플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘이다.
모든 지점에서 다른 모든 지점까지의 최단 거리를 저장하기 때문에 2차원 테이블에 최단 거리 정보를 저장하며, 이는 DP 알고리즘에 속한다. 따라서 DP에서 배운 것처럼 점화식을 사용한다. 처음에는 모든 거리를 '무한'으로 두고, 각 노드를 거쳐서 갈 수 있는 방법을 탐색하며 최단 거리를 갱신한다.
예를 들면 1단계에서는 노드 3에서 노드 2으로 가는 기본 경로가 없어서 거리가 무한이었으나 1번 노드를 거쳐가게 되면 3 -> 1 -> 2 로 최단거리가 9가 된다. 9는 무한보다 작기 때문에 D32를 9로 갱신한다. 점화식으로 따지면 아래와 같다.
D32 = min(D32, D31+D12)
1번 노드에서 3번 노드로 가는 간선이 없어서 2단계까지 1-3 은 무한이었으나 2번 노드를 거쳐서 1 -> 2 -> 3 으로 이동하면 최단 거리가 4+7=11 이 된다. 점화식으로 따지면 아래와 같다.
D13 = min(D13, D12+D23)
이렇게 각각의 노드를 거쳐서 가는 경우를 고려하여 테이블을 갱신한다.
♠ 플로이드-워셜의 특징
- 데이크스트라와 달리 음의 간선을 사용할 수 있다.
- 플로이드-워셜의 시간 복잡도는 O(n^3) 이다. 노드의 수가 n개일 때, n번의 단계를 수행하여 단계마다 O(n^2)의 연산을 통해 '현재 노드를 경유지로 거쳐 가는 모든 경로'를 고려한다. 따라서 총 시간 복잡도는 O(n^3)이다.
♠ 플로이드-워셜 기본 코드
# 노드의 개수(n)과 간선의 개수(m) 입력
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().split())
graph[a][b] = c
# 각 노드(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])
♠ 플로이드-워셜 알고리즘 문제 풀기
백준 알고리즘 11404번: https://www.acmicpc.net/problem/11404
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
m = int(input())
#2차원 그래프 만들기
inf = 1e9
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 i in range(m):
a, b, c = map(int, input().split())
graph[a][b] = min(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 i in range(1, n+1):
answer = graph[i][1:]
answer = [0 if x==inf else x for x in answer]
print(*answer)
♠ 참고 자료
알고리즘 다익스트라, 플로이드-워셜
그래프에서의 최단 경로 알고리즘인 다익스트라와 플로이드-워셜을 복습 경 정리해본다.
velog.io
https://takeknowledge.tistory.com/153
최단 경로 찾기 알고리즘 (다익스트라 / 플로이드 워셜) (python)
최단 경로를 찾는 알고리즘 중 대표적인 두가지로는 다익스트라 알고리즘과 플로이드 워셜 알고리즘이 있습니다. 다익스트라 알고리즘 - 개념 다익스트라 알고리즘은 출발 노드에서 특정 노드
takeknowledge.tistory.com
[알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)
지난 포스팅에서는 다익스트라 알고리즘에 대해 작성했었다. 다익스트라의 경우 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 그러나 모든 지점에서 다른 모든 지점까
velog.io
https://banwolcode.tistory.com/33
플로이드-워셜 알고리즘 (Floyd-Warshall)
플로이드-워셜 알고리즘 다익스트라가 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이라면 플로이드-워셜 알고리즘은 모든 노드 간의 최단 경로를 구하는 알고리즘이다. 그
banwolcode.tistory.com
플로이드-워셜 알고리즘
플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)은 그래프 에서 가능한 모든 노드 쌍에 대해
namu.wiki
'알고리즘' 카테고리의 다른 글
| 투 포인터(백준 알고리즘 2470번) (0) | 2024.10.27 |
|---|---|
| 세그먼트 트리 (0) | 2024.10.22 |
| BFS(너비우선탐색) vs DFS(깊이우선탐색) (0) | 2024.09.06 |
| 슬라이딩 윈도우(백준 알고리즘 12847번) (0) | 2024.09.05 |
| 플로이드 워셜 알고리즘(Floyd Warshall Algorithm, 백준 알고리즘 2458번) (0) | 2024.08.21 |