플로이드 와샬(Floyd-Warshall)

플로이드 와샬(Floyd Warshall)이란?

다익스트라는 하나의 정점에서 출발했을 때 다른 모든 정점으로의 촤단 경로는 구하는 알고리즘이다. 하지만 만약에 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 된다.

다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 특징이 있다.

• 시간 복잡도 O(n^3)
• 다 대 다 최단 거리를 구할 때 쓰는 알고리즘
• 음의 가중치를 가진 간선도 사용 가능
• 모든 정점에 대한 경로를 계산하므로 그래프가 아닌 2차원 배열 형태를 사용
• dp 방식으로 이전에 구한 값을 이용하여 갱신함

예시

• INF는 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻이다.

• ROUND 1 : 1번 노드를 새로운 중간 노드로 설정
• 이 그래프는 1번부터 5번 노드까지 존재하므로 알고리즘은 총 5번의 과정을 거친다.
• 즉 모든 노드들을 중간 노드로 선정하는 과정을 각 라운드마다 거친다.
• 2번 에서 4번으로 가는 길은 없었으나, 1번 노드를 중간 노드로 선정할 경우 2-1-4(길이 5+9)로 갈 수 있게 된다. (업데이트된 길이는 📍로 표시)

• ROUND2 : 2번 노드를 새로운 중간 노드로 설정
• 1번-3번 노드를 잇는 경로, 3번-5번 노드를 잇는 경로가 새로 생기게 된다.

• 이런 과정으로 5번 노드를 중간 노드로 선정하는 라운드까지 모두 거치면 행렬에는 모든 노드 간 최단 거리가 들어가게 된다.

코드

for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

 

 

출처

• chanhuiseok.github.io/posts/algo-50/
• ghdic.github.io/algorithm/floyd-warshall/#%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACfloyd-warshall%EC%9D%B4%EB%9E%80
• blog.naver.com/ndb796/221234427842