[플로이드 와샬]

<알고리즘 설명>

 

모든 정점에서 모든 정점으로의 '최단 경로'를 구하는 알고리즘.

 

거쳐가는 정점을 기준으로 최단 거리를 구한다.

 

즉, 

 

A라는 정점과 B라는 정점이 있고, 거쳐가는 정점 C가 있다고 치면

 

1.A에서 B로 바로가는 A-B 거리와

 

2.A에서 C를 거쳐 B로 가는 A-(C)-B 거리가 있을텐데

 

두 개의 대소비교를 통해 A-(C)-B < A-B 라면 해당 거리는 A-(C)-B로 갱신되고 계속해서 이 과정을 반복하는 알고리즘 이다.

 

---

따라서 해당 알고리즘을 구현하기 위해서는

 

1.모든 정점을 돌면서 각 정점에서 다른 정점까지의 거리가 거쳐가는 정점 거쳤을 때의 거리를 대소비교하며 갱신할 필요가 있다.

 

//k는 거쳐가는 정점
for(int k=0; k<n; ++k) {
	//i는 출발 정점
	for(int i=0; i<n; ++i) {
    	//j는 도착 정점
    	for(int j=0; j<n; ++j) {
        	if(graph[i][k] + graph[k][j] < graph[i][j])
            	grpah[i][j] = graph[i][k] + graph[k][j];
        }
    }
}

 

<참고 문제>

-백준 11403번 경로찾기

백준 www.acmicpc.net/status?user_id=slckscool&problem_id=11403&from_mine=1

채점 현황

#include <iostream>
#include <vector>

#define N 101


using namespace std;

vector<int> graph[N];
int n;

void flyoidWashall() {
	
	for (int k = 0; k < n; ++k)
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (graph[i][k] + graph[k][j] > 1 && !graph[i][j])
					graph[i][j] = 1;
}

void printGraph() {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			cout << graph[i][j] << " ";
		cout << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
	for (int i = 0; i < n; ++i) {
		graph[i] = vector<int>(n, 0);
	}

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> graph[i][j];

	flyoidWashall();
	printGraph();

}

 

 

-백준 11404번 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

#include <iostream>
#include <vector>

#define INF 987654321
#define CITY 102
#define BUS 100001

using namespace std;


vector<int> map[CITY];
int N, M;
int a, b, c;

void floyidWasshal() {
	
	for (int k = 1; k <= N; ++k) 
		for (int i = 1; i <= N; ++i) 
			for (int j = 1; j <= N; ++j) 
				if (map[i][k] + map[k][j] < map[i][j])
					map[i][j] = map[i][k] + map[k][j];
			
		
	
}

void printMap() {
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			if (map[i][j] == INF || i==j) cout << 0 << " ";
			else cout << map[i][j] << " ";
		}
		cout << '\n';
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; ++i) {
		map[i] = vector<int>(N+1, INF);
	}

	for (int i = 0; i < M; ++i) {
		cin >> a >> b >> c;

		map[a][b] = map[a][b] > c ? c: map[a][b];
	}

	floyidWasshal();
	printMap();
	
}

 

 

<참고 블로그>

blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘