Search
Duplicate
⚙️

플로이드 와샬

•
개요
◦
벨만포드나 다익스트라는 하나의 정점으로부터 다른 모든 정점까지의 최단거리를 구해야하는 SSP(Single Source Shortest Path) 문제였다.
◦
플로이드 와샬은 그래프에 존재하는 모든 정점들에 대해서 각 정점들이 다른 정점까지 도달하기 위한 최소 비용 거리를 구하는 문제이다.
•
개념
◦
어떤 정점 X부터 Y까지의 최단 거리를 구하기 위해 중간에 거쳐갈 수 있는 모든 정점들을 확인해보고 그 중 최소 비용 거리를 만드는 경로를 찾는 것이다.
dij(k)={wijif k = 0,min(dij(k−1),dik(k−1)+dkj(k−1))if k≥1.d_{ij}^{(k)}=\begin{cases} w_{ij} &\text{if k = 0,}\\ \text{min}(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}) &\text{if k} \geq 1. \end{cases}
◦
k = 0
▪
i, j가 바로 연결된 경우를 의미한다. 이는 정점 i, j 사이의 간선 거리의 비용을 의미하므로 wijw_{ij}라고도 할 수 있다.
◦
k > 0
▪
k가 0보다 크다는 것은 i부터 j까지 가는 길에 경유할 수 있는 정점이 존재한다는 것을 의미한다.
▪
이 경우, i, j간 간선 거리와 i, k 간, k ,j 간 간선 거리의 합 중 최소 비용을 최단 경로 비용으로 정한다.
•
구현
◦
O(n^3)의 시간 복잡도를 가지는 알고리즘이다.
1.
두 개의 2차원 배열을 초기화한다. 하나는 현재까지 계산된 최단 거리를 저장하고 다른 하나는 해당 최단거리를 만드는 바로 이전 정점을 저장하게 된다.
•
연결되어있지 않은 정점끼리는 무한으로 표시하고 이전 정점이 존재하지 않는 경우에는 null로 표시한다.
2.
각 노드를 거쳐가는 경우에 대해서 최소 비용을 구한다.
•
X → Y 비용 vs X -> Z 비용 + Z -> Y 비용
3.
2번 과정을 각 노드에 대해 반복한다.
Made with