플로이드 와샬 알고리즘

플로이드 - 워셜(와샬) 알고리즘 (Floyd-Warshall Algorithm) 

동적 계획법에 속하는 알고리즘으로, 그래프에서 모든 꼭지점 사이의 최단 경로를 구하는 알고리즘이다. 

음수 가중치를 갖는 간선도 순환만 없다면 문제없이 알고리즘이 동작된다. 

3중 for문으로 구현되며, 구성은 다음과 같다.

• 가장 바깥쪽 for문 : 거쳐가는 꼭지점
• 두 번째 for문 : 출발 꼭지점
• 세 번째 for문 : 도착하는 꼭지점이다. 

시간복잡도는 for문이 3개인 관계로 O(n^3)이다.

---

for(int k = 0; k < n; ++k){ //거쳐가는 꼭지점 
    for(int i = 0; i < n; ++i){ //출발 꼭지점 
        for(int j = 0; j<n; ++j){ //도착 꼭지점
            if(d[i][j] > d[i][k] + d[k][j]){
                d[i][j] = d[i][k] + d[k][j]
            }
        }
    }
}

여기서 지켜져야할 규칙은 다음과 같다. 

• 같은 정점끼리는 0으로 초기화한다. 
• 만약 두 정점간의 연결이 없다면 무한대의 값으로 초기화한다. 

무한대로 초기화하는 이유는 이 무한대를 이용하여 두 정점간의 연결 여부를 파악하기 위해서이다. 

즉, 무한대의 값이 아니라면 두 정점은 연결되어있다는 의미이다. 

---

예를들어 노드 1에서 노드 4로 도착하는 최단경로를 구한다고 가정하자.

---

d[1][4] = d[1][k] + d[k][4]

---

이제 저 k에는 [1]과 [4]의 경우를 제외한 나머지 값들이 들어가며 순서대로 계산을 진행하게 된다. 

 

같은 정점(1,4)이거나 연결되지 않은 경우는 걱정할 필요가 없다. 

위에서 같은 정점은 0으로 초기화되어있으며, 연결되지 않은 경우 무한대로 초기화 되어있기 때문이다.

---

개념정리에 도움을 준 사이트 : mygumi.tistory.com/110

플로이드 와샬 알고리즘 :: 마이구미