알고리즘 - 플로이드-워셜(Floyd-warshall)

플로이드-워셜

---

그래프에서 최단 거리를 구하는 알고리즘 중 하나로 다른 최단 거리를 구하는 알고리즘과 차이는 모든 노드 간에 최단 경로를 탐색한다는 것이다.

음수 가중치 에지가 있어도 수행할 수 있지만 음수 사이클이 있으면 안 된다.

동적 계획법의 원리를 이용해 알고리즘에 접근한다.

시간 복잡도는 O(V³) 으로 느린 편에 속하기 때문에 주어진 노드가 적을 경우에 사용한다.

 

플로이드-워셜의 핵심 이론

최단 경로 구하기

A 노드에서 B 노그까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 결국 최단 경로는 각 노드간 최단 경로가 합쳐졌다는 것을 의미한다.

플로이드-워셜 점화식: D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

1. 구현

인접 행렬로 리스트를 선언하고 초기화 한다.

인접 행렬로 초기화

인접 행렬로 초기화를 진행할 때 내 자신한테 가는 거리는 항상 0이기 때문에 자기 자신은 0으로 초기화를 해줘야 한다.

 

2. 최단 거리 리스트에 그래프 데이터 저장하기

그래프 데이터 저장

왼쪽의 그래프 데이터를 인접 행렬에 저장하면 오른쪽처럼 결과가 나오게 된다.

 

3. 점화식으로 리스트 업데이트 하기

업데이트 완료 후 인접 행렬

플로이드-워셜 점화식을 이용하여 모든 노드 간의 최단 거리를 구하는데 이때 3중 for문을 사용하여 구현한다.

for 경유지 K에 관해 (1 ~ N) {    // N: 노드 개수
      for 출발 노드 S에 관해 (1 ~ N) {
            for 도착 노드 E에 관해 (1 ~ N) {
                  D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
            }
      }      
}

※ 무한대로 표시한 곳은 갈 수 없는 곳을 의미한다.