플로이드 알고리즘 P - peulloideu algolijeum P

플로이드-워셜 알고리즘은 그래프에서 모든 점들의 쌍 (u, v) 간의 최단거리를 다 구하는 알고리즘이다.

경유점을 다음과 같이 정의하자.

u -> x1 -> x2 -> x3 -> x4 -> v 일때, x1, x2, x3, x4는 경유점.

즉, 어떤 경로에서 시작점과 끝점을 제외한 정점들을 의미한다.

이렇게 정의하고, DP 를 사용한다.

k-1번째 루프에서는 1~k-1의 정점들만을 경유점으로 하는 최단경로들의 값을 dp 테이블에 저장한다.

이제, 새로운 정점 k가 들어왔다고 생각하자.

최단거리는 k를 경유점으로 포함하는가, 하지 않는가로 나뉘고, 이는 다음과 같은 점화식으로 표현할 수 있다.

$dp[k][i][j]=min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])$

따라서 위 점화식으로 $N^3$ 루프를 돌며 계산해주면 된다.

여기서 공간복잡도를 $N^3$이 아닌 $N^2$ 으로 할 수 있는데, $dp[k-1][i][k]$와 $dp[k-1][k][j]$만 실제로 사용됨을 이용하면, 1~k-1 까지만 이용해서 i에서 k로 가는 최단거리나, 1~k만 이용하여 i에서 k로 가는 최단거리는 똑같다.

이를 이용하면 슬라이딩 윈도우를 하지 않고도 dp 테이블을 $N^2$ 만 사용하여 채울 수 있다.

for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);

음수 간선이 존재할 때, 음수 사이클 판별, 실제 경로 복구와 같은 추가적인 작업들을 할 때에는 주의할 점이 있다.

음수 간선이 존재할 경우

$dist[i][j]=min(dist[i][k]+dist[k][j], dist[i][j]);$ 에서 dist[i][k], dist[k][j] 중 하나는 INF 이고, 하나는 음수간선이면 INF 와 INF-1 을 비교하는 꼴이 된다. 이를 방지하기 위하여 dist[i][k]와 dist[k][j]가 모두 INF 가 아닐때만 연산을 해 주어야 한다.

최적화

위 조건 dist[i][k], dist[k][j]가 모두 INF가 아니라는 조건을 이용하면 k, i가 결정된 두번째 for문 다음에 INF의 확인을 통해 코드를 최적화할 수 있다.

실제 경로 복구

par[i][j] 배열에 i -> j 경로상에 마지막으로 드르는 k 정점을 저장해 논다. 즉, dist가 갱신될 때마다 par도 갱신되면, 그 경로상의 경유점들 중 최대값을 알 수 있고, 만약 모든 par 값들이 주어진다면, 재귀호출을 통하여 실제 경로도 복구할 수 있다.

음수 사이클 판별

기본적으로 dist[i][i]=0 이다. 만약에 갱신을 반복하던 중, dist[i][i]가 음수가 된다면 이는 음수 사이클이 존재한다는 점이고, 이로 판별할 수 있다.

시간 복잡도 : $O(N^3)$

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 100; const int INF = 987654321; int n, m, s, e; int dist[MAXN+10][MAXN+10], par[MAXN+10][MAXN+10]; bool negcycle; void restore(int s, int e) { if(par[s][e]==0) return; restore(s, par[s][e]); printf("%d ", par[s][e]); restore(par[s][e], e); } int main() { int i, j, k; scanf("%d%d", &n, &m); for(i=1; i<=n; i++) for(j=1; j<=n; j++) dist[i][j]=INF; for(i=1; i<=n; i++) dist[i][i]=0; for(i=0; i<m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dist[u][v]=min(dist[u][v], w); } for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) { if(dist[i][k]!=INF && dist[k][j]!=INF) { if(dist[i][j]>dist[i][k]+dist[k][j]) { dist[i][j]=dist[i][k]+dist[k][j]; par[i][j]=k; } } } for(i=1; i<=n; i++) { for(j=1; j<=n; j++) printf("%d ", dist[i][j]); printf("\n"); } while(1) { scanf("%d%d", &s, &e); printf("%d ", s); restore(s, e); printf("%d\n", e); } }

C 언어로 최단경로 알고리즘 (Floyd Algorithm)

추천글 : 【C 언어】 C 언어 목차

a. GitHub 

문제상황. 예를 들면 0번 &rarr; 5번으로 가는 경로는 6만큼의 비용이 든다.#include <stdio.h> #include <stdlib.h> #define Count_Vertice 6 #define Far_Distance 2000 int W[Count_Vertice][Count_Vertice] = { // W[i][j]는 i에서 j까지의 직행거리, Far_distance란 큰 수는 바로 갈 수 없는 경우를 표시 {0, Far_Distance, 2, 3, 3, 6}, {Far_Distance, 0, Far_Distance, 4, 2, Far_Distance}, {10, 2, 0, 5, 1, Far_Distance}, {Far_Distance, Far_Distance, 4, 0, Far_Distance, 2}, {5, 9, Far_Distance, 4, 0, 3}, {Far_Distance, Far_Distance, Far_Distance, 4, Far_Distance, 0}, }; int D[Count_Vertice][Count_Vertice]; // D[i][j]는 i에서 j까지 가는 최소 거리를 저장 int P[Count_Vertice][Count_Vertice]; // P[i][j]는 i에서 j까지 가는 데 거치는 최고 차수 정점을 저장 void Floyd(){ int i, j, k; for(i=0; i < Count_Vertice; i++) // 배열 초기화 for(j=0; j < Count_Vertice; j++){ P[i][j] = -1; D[i][j] = W[i][j]; } for(k=0; k < Count_Vertice; k++) for(i=0; i < Count_Vertice; i++) for(j=0; j < Count_Vertice; j++) if(D[i][j] > D[i][k] + D[k][j]){ /* k를 거칠 시 D[i][j]가 더 짧아지는 경우 */ D[i][j] = D[i][k] + D[k][j]; P[i][j] = k; } } void Print_Path(int a, int b){ // Print_Path[i][j]에서 i와 j는 출력하지 않음을 주의 if(P[a][b] != -1) { // P[a][b] = -1 "=" a에서 바로 b로 가는 것이 최단거리 Print_Path(a, P[a][b]); printf("%d ", P[a][b]); Print_Path(P[a][b], b); } } int main(int argc, char *argv[]){ Floyd(); int a, b; printf("출발점과 도착점을 입력하시오. (0 ~ %d)\n", Count_Vertice - 1); scanf("%d %d", &a, &b); printf("최단거리 : %d\n", D[a][b]); printf("최단경로 : "); printf("%d ", a); Print_Path(a, b); if(D[a][b] != 0) printf("%d", b); // D[a][b] = 0 "=" a = b return 0; }