[Algorithm] 모든 쌍 최단 경로 | Floyd-Warshall Algorithm

이전에 포스팅했던 모든 쌍 최단 경로, 다익스트라 알고리즘을 이용하는 법과 또다른 알고리즘 방식인 

Floyd-Warshall 알고리즘에 대해 기록해보고자 한다!

 

이전의 다익스트라 알고리즘,,

• 각 점을 시작점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행
• 시간복잡도는 배열을 사용하면 (n-1) x O(n^2) = O(n^3) 

---

 

Floyd-Warshall 알고리즘 (플로이드-워샬)?

💡접근법

• 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.
• 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다.

💡동적 계획 알고리즘으로 접근하기 위해, 먼저 부분 문제들을 찾는다.

• 그래프에 점이 3개 있는 경우, 직접 가는 경로와, 점 하나를 거쳐 경유하는 경로 두가지 중 최소 거리를 선택하면 된다.
• 즉, 중요한 아이디어는 경유 가능한 점들을 고려해야한다는 것이다. (경유 가능한 점들이 많을 경우?!)

💡점 i에서 점 k를 경유하여 j로 가는 경로 중 짧은 경로 찾기 (k인 경우 : 점 1,2,3...k를 경유 가능한 점들로 고려하는 경우)

• 이런 방식으로 k가 1에서 n(=입력 점들)이 될 때까지 D^k(ij)를 계산해서, D^n(ij) 모든 점을 경유 가능한 점들로 고려된 모든 i ,j 쌍의 최단 경로의 거리를 찾는 방식이 플로이드의 모든 쌍 최단 경로 알고리즘!

 

 

 

➰의사코드 

• 입력 : 2차원 배열 D, 단, D[i, j]=선분 (i, j)의 가중치, 만일 선분 (i, j)이 존재하지 않으면 D[i, j] = ∞, 모든 i에 대하여 D[i, i] = 0임
• 출력 : 모든 쌍 최단 경로의 거리를 저장한 이차원 배열 D

1. for k=1 to n		// 경유 가능한 점들을 1부터 n까지 확정
2. 	for i=1 to n (i!=k)
3. 	  for j =1 to n (j!=k, j!=i)	// 점들의 각쌍을 하나씩 고려하기 위한 루프 2,3
4. 		D[i,j]= min{D[i,k]+D[k,j], D[i,j]}		// D[i,j] 갱신, 부분 문제 간 함축적 순서 표현

• k=0, k=1, ... k=n 일때까지 이차원 배열을 계속 업데이트 해나간다.
• line 4 = 함축적 순서 표현 -> 새로운 D[i,j]를 계산하기 위해서 미리 계산되어 있어야 할 부분 문제들은 D[i,k] 와 D[k,j] 이다.

  

여기서 입력 그래프에는 사이클 상의 선분들의 가중치 합이 음수가 되는 사이클은 없어야 한다.
이러한 사이클을  '음수 사이클'이라고 하는데, 최단 경로를 찾는데 음수 사이클이 있으면, 이 사이클을 반복하여 돌아 나올때마다 경로의 거리가 감소되기 때문이다.

 

➰CPP 코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int > > arr;

int Min(int a, int b){
    if(a<b){
        return a;
    }
    return b;
}

int main(){
    int n; //노드의 수
    cin >> n; 

    for(int i=0;i<n;i++){
        vector<int>element(n);   
        arr.push_back(element);
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> arr[i][j];
        }
    }
    
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            if(i!=k)
            {
                for(int j=0;j<n;j++){
                    if(j!=k && j!=i){
                        arr[i][j] = Min(arr[i][k]+arr[k][j], arr[i][j]);
                    }
                }
            }
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<arr[i][j]<<' ';
        }
        cout<<'\n';
    }
}

 

 

➰공부흔적

 

 

 

➕경유지가 뭐인지 알고 싶다면 추가할 코드!

 for k=1 to n	
 	for i=1 to n (i!=k)
    	for j =1 to n (j!=k, j!=i)
			if(D[i][k] + D[k][j] < D[i][j]){
            	D[i][j] = D[i][k] + D[k][j];
                P[i][j] = k; //추가! (k=경유지 값!)
             }

 

⏰시간복잡도

• 각 k에 대해서 모든 i,j 쌍에 대해 계산되므로, 총 nxnxn=n^3회 이루어지고, 각 계산은 O(1) 시간이 걸린다
• 따라서 O(n^3)
• 다익스트라 알고리즘과 시간 복잡도는 같지만 알고리즘 자체는 훨씬 간단하다

 

 

 

---

응용

• 맵퀘스트와 구글 웹사이트의 지도 서비스
• 자동차 네비게이션 서비스
• 지리정보시스템에서의 네트워크 분석
• 통신 네트워크와 모바일 통신 분야
• 게임
• 산업 공학, 경영 공학의 operations Research
• 로봇 공학
• 교통 공학
• 디자인 분야 등

 

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업