Floyd-Warshall 알고리즘

그래프에서 모든 정점에서 모든 정점 쌍 사이의 최단 거리(최소 비용)를 구하는 알고리즘

다익스트라 알고리즘과 벨만-포드 알고리즘은 특정 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 거였다.

 

출발 정점, 도착 정점을 모두 고려해야 하므로 DP 테이블은 2차원으로 구성되어야 한다. 

그리고 최단 거리 갱신을 위한 점화식이 필요하다.

2차원 형태의 dis 배열 준비 

dis[i][j]는 i번 노드에서 j번 노드로 이동하는 데 드는 최소 비용

초기에는 dis 테이블을 인접 행렬 기준으로 초기화한다. 

이는 중간에 어떤 노드도 거치지 않고 i에서 j로 바로 가는 경우의 비용을 의미한다.

 

예를 들어, dis[1][2]에는 1번 노드에서 2번 노드로 직접 이동할 때 드는 비용을 기록한다.

마찬가지로 2- >4 는 1이다. 

M은 두 노드 사이에 직접 이동할 수 없는 경우(큰 값으로)

예를 들어 1번 노드에서 4번 노드로 직접 이동하는 간선이 없어 dis[1][4]=M으로 초기화

 

즉, 1행은 1번 노드에서 1, 2, 3, 4, 5번 노드로 이동할 때의 최소 비용을 저장한다.

2, 3, 4, 5행도 마찬가지

일반적으로 노드의 개수가 n개라면, dis 테이블은 1번부터 n번까지 적어놓을 수 있다. 

---

이렇게 테이블을 초기화한 뒤, 다음으로 고려해야 할 것은 중간 경유 노드를 포함한 최단 거리 계산이다.

i->j의  최소 비용을 구할 때,

i와 j 사이에는 1~n번까지의 여러 정점이 중간 경유지로 포함될 수 있다.

 

예를 들어 i→j로 갈 때

1) 1번 노드만 거쳐서 가는 경우도 있고,
2) 1번과 2번 노드를 거쳐 가는 경우, i → 2 → 1 → j와 같이 다양한 경로가 존재할 수 있다.

3) 중간 노드로 1~3번을 허용한다면, i → 1 → 2 → 3 → j, i → 2 → 1 → 3 → j 등등등 여러 순서의 경로가 가능하다.

4) 또 1~4번 노드를 모두 경유하는 경로도 존재할 수 있다. 

 

즉, 중간 노드를 전혀 사용하지 않는 경우부터
1번 노드만 사용하는 경우,
1번과 2번 노드를 사용하는 경우 등 여러 단계의 경우를 차례대로 고려한다.

이 중에서 가장 작은 비용을 가지는 값이 최단 거리가 된다.
그리고 이때 중간 경유 노드에는 출발 노드 i와 도착 노드 j는 포함하지 않는다.

 

노드 번호가 1~n까지 있다고 할 때,
중간 경유지로 1번 노드만 허용한 경우, 1번과 2번 노드를 허용한 경우,
이런 식으로 허용하는 중간 노드의 범위를 점점 늘려가며 모든 경우를 계산한다.
그리고 그중 가장 작은 비용을 2차원 DP 배열(dis)에 반영한다.

dis[i][j]는 기존의 최단 거리 값과,

중간에 k번 노드를 거쳐 i → k → j로 이동했을 때의 비용을 비교하여 더 작은 값으로 갱신한다.

 

k=1일 때는, 모든 i와 j에 대해 2중 반복문을 돌면서
“1번 노드를 거칠 수 있는 경우”를 기준으로 값을 갱신한다.

즉 k=1에 대한 갱신이 끝나면,
DP 테이블에는 직접 이동하는 경로와 1번 노드를 거쳐 가는 경로 중 더 좋은 값이 저장되어 있다.

 

k=2가 되면 다시 모든 25개를 돌면서 
2번 노드를 중간 경유지로 사용하는 경우를 고려한다.

 

같은 방식으로 k가 3, 4, …, n이 될 때까지 이 과정을 반복한다.

 

이러한 과정을 모두 거쳐 갱신이 완료되면

i → j로 직접 가는 경우,
1번 노드를 거쳐 가는 경우,
1번과 2번 노드를 경유할 수 있는 경우를 모두 고려한 최단 거리가 저장된다.

 

이떄 k를 1부터 2까지 순서대로 처리했기 때문에,
경로가 반드시 i → 1 → 2 → j의 순서일 것처럼 보일 수 있다.

하지만 실제로는 그렇지 않다.
이 방식은 중간 노드로 사용할 수 있는 집합을 확장하는 것일 뿐,
실제 경로의 순서는 i → 2 → 1 → j처럼 어떤 순서든 가능하다.

 

이제 중간 경유지로 3번 노드까지 허용한 상태(k=3)에서,
모든 i, j에 대해 2중 반복문을 수행한다고 가정하자.

이 상태에서 dis[5][4], 즉 5번 노드에서 4번 노드로 가는 최소 비용을 갱신해보자.

k=3이므로, 기존 dis[5][4] 값과
3번 노드를 거쳐 가는 경로, 즉 dis[5][3] + dis[3][4]를 비교한다.

dis[5][3] + dis[3][4]는 단순히
5 → 3 → 4 형태만 의미하는 것이 아니라,
1번과 2번 노드를 포함한 다양한 경로가 이미 반영된 결과값이다.

즉, 5 → 3으로 가는 경로는
직행뿐만 아니라 5 → 1 → 3, 5 → 2 → 3, 5 → 1 → 2 → 3 등
가능한 모든 경우 중 최소 비용만 남아 있다.

dis[5][3]은 이미 k=1, k=2 단계를 거치며,
1번과 2번 노드를 중간 경유지로 사용할 수 있는 모든 경우가 반영된 최소 비용이기 때문다. 

 

dis[3][4] 역시 1번과 2번 노드를 경유지로 사용할 수 있는 경우까지
이미 고려된 최단 거리 값이다.

결과적으로 dis[5][3] + dis[3][4]는
5 → 2 → 3 → 1 → 4와 같은 경로를 포함할 수도 있으며,
중요한 것은 이 모든 경우 중 최소 비용만 사용된다는 점이다.

 

여기서 중요한 것은 DP 테이블이 “경로 자체”가 아니라 “최소 비용”을 저장한다는 점이다.

플로이드-워셜은 경로의 순열을 나열하는 알고리즘이 아니라,
중간 경유 노드의 허용 범위를 점진적으로 확장하는 DP 알고리즘이다.

k=5까지 모든 반복이 끝나면,
dis[i][j]는 1번부터 5번 노드를 중간 경유지로 사용할 수 있는 모든 경우를 고려한 최단 거리가 된다.

이는 모든 노드를 반드시 사용하는 경로를 의미하는 것이 아니라,
1개, 2개, 혹은 아무 중간 노드도 사용하지 않는 경우까지 모두 비교했다는 뜻이다.

 

 

dis[5][3], dis[3][4]도 이미 k=3이 적용됐는데
다시 쓰면 중복 아니냐?

전혀 문제가 되지 않는다.
dis[3][3] = 0이기 때문에
i → 3 → 3 → j와 같은 중복 경로는
비용을 증가시키지 않으며 자연스럽게 무시된다.

 

 

코드

//int n,m,a,b,c;
cin>>n>>m;
vector<vector<int>>dis(n+1,vector<int>(n+1,5000)); /dp 테이블 초기화
for(int i=1;i<=n;i++) dis[i][i]=0; // 대각 선을 0으로 초기화 자기 자신한테 가는거
for(int i=1; i<=m; i++){
	cin>>a>>b>>c;
	dis[a][b]=c;
}
//인접 행렬 초기화 
-> 이 for문 만 돈 dis는 i->j로 바로 갔을때에 최소 비용값들이 있다. 


//이 3중 for문이 플로이드 와샬 
for(int k=1; k<=n; k++){ //i->k->j일 때 k 1일 때 이차원 다 훑고 k 2일 때 다 훑고 등등
	for(int i=1; i<=n; i+){
		for(int j=1; j<=n; j++){
			if(dis[i][j]>dis[i][k]+dis[k][j]){ //기존값하고 i->k->j로 가는거하고 비교해서 작으면 바꿔라 
				dis[i][j]=dis[i][k]+dis[k][j];
			}
		}
	}
}

 

 

 

 

출처: it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++)