-
Floyd-Warshall알고리즘 2020. 3. 17. 15:29
그래프에서 정점끼리의 최단 경로를구하는 문제 중
다익스트라에 이어 플로이드 워셜 알고리즘에 대해 알아보도록 하자.
Floyd-Warshall Algorithm 플로이드 워셜 알고리즘
- 개념 : 모든 정점끼리의 최단 거리를 구하는 알고리즘
- (다익스트라가 한 정점에서 다른 정점들까지였다면, 플로이드는 모든 정점들을 다 구하는 방법이다.)
- (각 정점을 시작점으로 다익스트라 알고리즘을 반복하여도 되지만, 플로이드는 단 한번의 시행으로 모든 쌍을 구할 수 있다.)
- 속성
Optimal substructure - 최단 경로의 부분경로는 역시 최단 경로다.
(특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념)
작동 방식
- 정점(1,2, … , k) 이 있다고 가정해보자.
- C(k,u,v) : 1번 정점부터 k번 정점까지만을 경유점으로 썼을 때,
u에서 v까지 가는 최단 경로의 길이 u -> v / u -> (1,….,k) -> v
- C(k,u,v) = min(C(k,u,k) + C(k,k,v) , C(k,u,v))
- (u,v)로 가는 최단 경로에는
1) k를 거쳐가는 최단 경로
2) k를 거치지 않는 최단 경로
두가지가 존재한다.
- 위 점화식을 사용하여 코드 작성
모든 정점에 대한 경로를 계산하므로, 거리를 저장할 자료 구조는 다익스트라와 달리 2차원 배열을 사용한다.
Dist[u][v] : 정점u에서 정점v로 가는 최단 거리
다익스트라와 달리 음수 가중치에서 사용이 가능하다.
(ex) 100개까지의 정점이 존재한다고 할때, 모든 정점들 사이의 최단 거리를 구하는 프로그램을 만들어보자.
123456789101112131415161718192021222324int n; //정점의 개수int INF = 999999999;int adj[101][101]; //거리를 저장하는 배열, 처음 초기값은 INF로 설정void Floyd() {for (int i = 1; i <= n; i++) {adj[i][i] = 0; //자기 자신의 거리는 0으로 초기화}//k = 거쳐가는 노드for (int k = 1; k <= n; k++) {//i = 출발 노드for (int i = 1; i <= n; i++) {//시간 단축의 방법 ? i->k 경로가 있는지 확인, 없으면 passif(adj[i][k] == INF) continue;//j = 도착 노드for (int j = 1; j <= n; j++) {adj[i][j] = min(adj[i][k] + adj[k][j], adj[i][j]);}}}}cs '알고리즘' 카테고리의 다른 글
Segment Tree (0) 2020.03.17 Greedy Algorithm (0) 2020.03.17 Dijkstra (0) 2020.03.17 Binary Serach (0) 2020.03.16 DP (0) 2020.03.16