[baekjoon 11404] 플로이드 (플로이드-와샬) (C++)

www.acmicpc.net/problem/11404

11404번: 플로이드

기본적인 플로이드 와샬 알고리즘을 사용해서 푸는 문제이다.

 

다익스트라와 같이 최단 거리를 찾는 알고리즘이지만, 차이점을 한번 비교해보았다.

 

다익스트라 VS 플로이드-와샬

 

1. 최단거리를 찾는 경로

- 다익스트라 : 어떤 한 점에서 목적지까지의 최단 거리를 업데이트

- 플로이드 : 모든 정점에서 모든 정점까지의 최단 거리

 

-> 단일 경로의 최단 거리를 찾는 것은 다익스트라가 훨씬 빠르다.

 

2. 최단 거리를 찾는 방법

- 다익스트라 : 어떤 한 점에서 연결된 점들 중 가장 적은 비용 기준으로 나아가면서 거리를 업데이트

(최단 비용의 점을 선택해서 나아가므로 이미 방문한 점은 최단 거리로 업데이트되어 있는 상태)

 

- 플로이드 : 어떤 한 점에서 다른 점까지 가는 길 중 거쳐가는 정점 기준으로 거리를 업데이트

(모든 점을 돌면서 A-B의 거리를 A-B 중 거쳐갈 수 있는 정점들의 거리를 포함해서 계산)

(A-B가 5인데, A-C가 1 + C-B가 2이면 C를 거쳐감으로 A-B의 거리는 3이 최단거리가 될 수 있다.)

 

3. 음의 가중치

- 다익스트라 : 다익스트라는 음의 가중치일 경우 사용이 불가능하다.

- 플로이드 : 음의 가중치도 사용 가능

 

4. 시간 복잡도(정점 : V, 간선 : E)

- 다익스트라 : 인접 행렬(V^2), 인접 리스트(ElogV)

- 플로이드 : V^3

 

그리고 플로이드가 코드가 훨씬 간단했다.

3중 for문을 돌면서 경유지-시작점-끝점 순으로 for문을 돌린다.

+ dp 개념을 사용한다.

 

#include <iostream>
#define INF 987654321

using namespace std;

int n, m, arr[101][101], from, to, cost;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			arr[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		if(arr[from][to] > cost)
			arr[from][to] = cost;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (j == k)
					continue;
				if (arr[j][k] > arr[j][i] + arr[i][k])
					arr[j][k] = arr[j][i] + arr[i][k];
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] == INF)
				cout << 0 << " ";
			else
				cout << arr[i][j] << " ";
		}
		cout << "\n";
	}
}

처음에 배열을 무한대로 채워주고, min값을 저장해주는 방식으로 진행한다. (최단 거리로 업데이트)

+ 만약 INF 상태이면 경로가 없는 것이므로 0을 출력해준다.