Floyd-Warshall

그래프에서 정점끼리의 최단 경로를구하는 문제 중

다익스트라에 이어 플로이드 워셜 알고리즘에 대해 알아보도록 하자.

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개까지의 정점이 존재한다고 할때, 모든 정점들 사이의 최단 거리를 구하는 프로그램을 만들어보자.

  

int 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 경로가 있는지 확인, 없으면 pass
            if(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]);
            }
            
        }
    }
 
}