Floyd-Warshall

플로이드 워셜

그래프를 구성하는 모든 정점 간에 최단 경로를 탐색하는 알고리즘

특징

• 음의 가중치를 가지는 간선이 있어도 사용 가능

• 합이 음의 값인 음의 가중치 사이클이 발생시 탐지 가능

장점

• 음수 가중치 처리 가능

• 방향 그래프와 무방향 그래프 모두 작동

• 구현하고 이해하는 것이 비교적 간단

• 정점의 개수가 1000개 이하일 때 사용 가능

단점

• 높은 시간 복잡도

• 중간 결과 저장시 많은 메모리 공간 필요

활용 조건

• 노드의 수보다 간선의 수가더 많을 때

• 노드의 수가 적을 때

• 음의 간선이 있을 때

동작 과정

그래프의 노드와 간선에 따라 최단거리 테이블을 생성하고 거리를 갱신한다.

• 바로 도착하는 거리와 경유해서 end 정점까지 도착하는 거리 중 작은 값으로 결과 테이블을 업데이트 한다.

• 다른 정점을 기준으로 반복한다 (n번 노드까지)

음수 사이클

두 간선 사이의 거리 합 < 0인 경우 음수 사이클 발생

시간복잡도

O($N^3$)이기 때문에 노드의 개수가 적을 때만 사용해야 한다. 구현시 삼중 for문을 사용하기 때문에 정점이 1000개만 되어도 반복문을 10억번 돌기 때문에 성능이 급격히 저하된다.

구현 정보

1. 간선의 정보를 담고 있는 2차원 배열 Integer[][] graph배열의 크기를 구한다.

2. graph정보를 이용하여 distrance배열에 노드간 연결 정보, 가중치를 초기화 한다.

3. 바로 도착하는 경우와 경유하는 경우를 나누어 노드를 바꿔가며 반복하여 결과 테이블을 업데이트 한다.

4. 다른 노드를 거쳐 자신에게 오는 경로의 값이 음수이면 루프 발생을 알린다.