1. 플로이드-와샬 알고리즘
•
모든 정점에서 모든 정점으로의 최단 거리를 한번에 구하는 알고리즘
•
O(N^3) 시간복잡도를 가지고 있다.
•
모든 정점쌍을 표현하는 이차원 배열을 선언하고 DP 방식으로 최단거리를 업데이트한다.
2. 플로이드-와샬 알고리즘
•
i행과 j열의 원소인 (i, j) 원소는 정점i로부터 정점j까지의 최단 경로를 뜻한다.
•
Dynamic Programming 방식으로 진행된다.
◦
점화식 
distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])▪
정점 i에서 정점 n을 거쳐서 정점 j로 갈 때, n을 거쳐 가는 것이 더 최단경로일 경우 업데이트 한다.
▪
이렇게 거쳐갈 정점을 차례대로 모두 검사하여 업데이트 해나간다.
3. 플로이드-와샬 알고리즘 프로세스
•
행렬 초기화
◦
그래프 모양을 참고하여 초기화 한다.
◦
직접적으로 인접하여 연결되어 있지 않은 정점들의 경우 INF 무한대로 초기화 한다.
◦
자기 자신과 자기 자신이 연결되어 있진 않기 때문에 행렬의 대각선은 모두 0 이 된다.
•
거쳐갈 정점들을 처음부터 차례대로 검사하여 해당 정점을 거쳐 가는 것이 더 최단 경로일 경우 원소를 업데이트 한다. 매번 행렬 전체 원소들에 대해 진행!!
◦
ex)
▪
정점 1 을 거쳐갈 때
•
기존의 (i, j) 원소값 보다 (i, 1) + (1 + j) 값이 더 작으면 이 값으로 업데이트. 아니면 냅두기.
•
즉 ! 정점 1 을 거쳐가는게 더 최단 경로일 경우 업데이트 하는 것이다.
▪
정점 2 을 거쳐갈 때
•
기존의 (i, j) 원소값 보다 (i, 2) + (2 + j) 값이 더 작으면 이 값으로 업데이트. 아니면 냅두기.
•
기존의 (i, j)는 정점 1 을 거쳐오는 경우도 고려해서 최단 경로를 업데이트 기존에 됐던 경우다.
•
정점 2 을 거쳐가는게 더 최단 경로일 경우 업데이트 하고 아니라면 정점 2 거쳐가지 말고 기존 값 그대로 냅두기 !
▪
이런식으로 모든 정점을 거쳐가는 경우를 쭉쭉 따져서 전체 행렬 원소들을 업데이트 해나가면 된다.
3.1 BFS 시간 복잡도
모든 i, j 에 대하여 중간에 k 라는 노드를 경유하는 모든 경우의 수를 계산하는 3중 반복문의 구조를 가지고 있으므로 시간복잡도는 O(N^3)이다.
3.2. 플로이드-와샬 구현
void floid() {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
C++
복사
