소피it블로그
[알고리즘] 플로이드 워셜 최단 경로 알고리즘 파이썬 구현 본문
자료 출처: https://youtu.be/acqm9mM1P6o
1. 플로이드 워셜 알고리즘
최단 경로 알고리즘으로, 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘의 경우 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘인데 반해, 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구한다는 점이 차이점이다.
- 거쳐가는 노드를 기준으로 알고리즘을 수행하는 것은 다익스트라 알고리즘과 동일하나, 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요 없다는 점이 다르다.
- 2차원 테이블에 최단 거리 정보를 저장한다.
- 다이나믹 프로그래밍 유형에 속하며, 삼중 반복문을 사용한다.
- 시간 복잡도는 O(N^3)
- 노드의 개수가 500개 미만일 때 사용 가능
- 각 단계마다 특정 노드 k를 거쳐가는 경우를 확인한다.
- a에서 b까지의 최단 경로 vs a에서 k를 거쳐 b로 가는 거리
- 점화식: Dab = min(Dab, Dak + Dkb)
2. 플로이드 워셜 알고리즘 구현
n, m = map(int, input().split())
inf = int(1e9)
# 그래프 초기화(2차원 리스트)
# 노드 넘버이기 때문에 (n + 1)을 곱해줌
# [inf]가 (n + 1)개 만큼 들어있는 리스트를 다시 (n + 1)개만큼 만들어 새로운 리스트에 넣어줌
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 = map(int, input().split()) # a에서 b로 가는 비용은 c
graph[a][b] = c
# 모든 노드들에 대하여 a에서 b로 가는 최단 경로 업데이트하기
for k in range(1, n + 1): # k는 거쳐가는 노드
for a in range(1, n + 1): # a는 출발 노드
for b in range(1, n + 1): # b는 도착 노드
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
'CS > 자료구조, 알고리즘 이론' 카테고리의 다른 글
[자료구조/알고리즘] 신장 트리, 최소 신장 트리, 크루스칼 알고리즘 파이썬 구현 (1) | 2022.10.01 |
---|---|
[자료구조] 서로소 집합 (0) | 2022.10.01 |
[알고리즘] 다익스트라 최단 경로 알고리즘 파이썬 구현 (0) | 2022.10.01 |
[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) (1) | 2022.09.30 |
[자료구조] 트리, 이진 탐색 트리 (1) | 2022.09.30 |