그래프 - 플로이드-와샬

플로이드 알고리즘은 모든 노드 쌍의 사이의 최소 비용을 구해주는 알고리즘이다.

플로이드 와샬 알고리즘은 N제한만 맞으면 사용하기 좋다.

 

 

예를들어서 아래와 같은 그래프가 존재한다고 해본다면,

플로이드 와샬 알고리즘을 적용하면 N1->N3에서 가는 최소값, N1->N2로 가는 존재하는 모든 쌍의 최소 거리 정보를 구할 수 있다.

 

물론 익히 알고있는 다익스트라알고리즘을 노드 개수만큼 V번 돌려서, 다익스트라(N1), 다익스트라(N2), 다익스트라(N3) 최소거리를 구할 수 있다. 하지만, 플로이드 와샬은 조금 더 간단하게 DP를 이용해서 문제를 해결한다.

 

 

DP를 하기 위해 함수를 소개하자면,

DP[x][y][k] 같은 3차원 배열을 채워나간다고 가정한다.

- x->y 를 방문한다.

- 단, 중간에 방문할 수 있는 점은 1...k 로 한정한다.

 

여기서 한가지 주목해야 할 점은 "중간에 방문할 수 있는 점은 1...k 로 한정한다." 부분이다.

플로이드 와샬의 DP의 정의는, 중간에 "방문할 노드 k를 기준으로 확장"한다.

다시말해서 x번째 노드 -> k번째 노드 -> y번째 노드 로가는데 최소값인지를 체크하는게 아니라,

x -> 1...k (1번부터 k번째까지 확장했을 때 현재까지의 최소값) -> y 으로 계산한다.

 

따라서, 식을 보고 x -> k -> y 처럼 단 3번만에 y노드에 도달하는 것처럼 오해하는 경우가 있는데

오히려 그것보다 x -> 1번노드 -> 3번노드 -> 4번노드 -> y 처럼 여러번의 노드를 탐색한다라는 의미로 사용한다.

 

어디에 사용할 수 있을까?

- 모든 쌍의 최소경로 (n^3) 이기 때문에 사실 시간 제한만 맞으면 다 사용 가능하다.

- dp로 구하는것이기 때문에 음수가중치도 문제없이 구할 수 있다.

 

수도코드를 보자면 아래와 같다.

 

1. 초기화 파트

2. DP파트.

3차원 이지만, 의미상으로는 2차원과 다를 바 없기 때문에 2차원 배열을 사용한다. 

* TODO

 

관련문제

www.acmicpc.net/problem/9205