[알고리즘 이론] Floyd Warshall 플로이드 와샬 알고리즘 C++

Floyd Warshall이란?

 

대표적인 최단거리 찾기 알고리즘 중 하나

- 다익스트라, 벨만포드, 플로이드 와샬

 * 다익스트라 : 모든 쌍의 최단 경로(음의 가중치 X)

 * 벨만포드 : 모든 정점에 대한 최단경로(음의 가중치 O)

 * 플로이드 와샬(음의 가중치 O + 음의  사이클이 없어야한다)

모든 정점끼리의 최단거리를 한번에 계산할 때 사용 + 동적 계획법을 사용

ex) 전체 정점에서 다른 정점들까지의 최단거리를 한번에 계산

-> 다익스트라의 경우 어떤 정점 A에서 다른 정점들까지의 최단 거리를 계산

 

 

Pseudo Code

for(k=1;k<=n;k++) //거쳐가는 노드
for(i=1;i<=n;i++) //출발 노드
for(j=1;j<=n;j++) //도착 노드
    D[i][j]=min(D[i][k]+D[k][j], D[i][j])

기존의 i 정점부터 j정점까지 이동했던 경로와 (i정점부터 k정점까지의 최단 경로) + (k정점부터 j정점까지의 최단 경로) 중 최소값을 저장

 

시간 복잡도

3중 for문을 사용하므로 O(V^3)

 

 

Floyd Warshall 예제 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();

	int N;
	cin >> N;
	int M;
	cin >> M;
	vector<vector<int>> dis(N+1,vector<int>(N+1,5000));
	for (int i = 1; i <= N; i++) {
		dis[i][i] = 0;
	}
	


	for (int i = 0; i < M; i++) {
		int from, to ,c;
		cin >> from >> to >> c;
		dis[from][to] = c;
	
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}

	for (int i = 1; i < N; i++) {
		for (int j = 1; j < N; j++) {
			cout << dis[i][j] << " ";
		}
		cout << "\n";
	}

}