[알고리즘] 플로이드 워셜

1. 개념

그래프 상에 있는 모든 경로의 최단 경로를 구할 수 있는 알고리즘이다. 즉, 노드 1 2 3 4 5 가 있을 때, 노드 1과 노드 2사이의 최단 경로, 노드 1과 노드 3 사이의 최단 경로....노드 4와 노드 5 사이의 최다 경로를 모두 구할 수 있다. 

출발 노드로부터 각 노드까지의 최단 경로를 구하는 다익스트라나 벨만포드 알고리즘과는 살짝 다르다.

 

2. 특징

• 모든 노드 간의 최단 경로를 탐색할 수 있다.
• 음수 가중치 에지가 있어도 수행할 수 있다.
• 동적 계획법의 원리를 이용해 알고리즘에 접근한다.
• 시간 복잡도가 O(V3)이다. V는 노드의 수.
• 인접 행렬을 이용하면 구현이 간단하다.

 

3. 원리

동적 계획법의 원리

시작 노드부터 도착 노드까지의 최단 경로는 시작 노드부터 중간 노드까지의 최단 경로와 중간 노드부터 도착 노드까지의 최단 경로의 연결로 이루어져 있다. 즉, 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어져 있다.

 

• 노드끼리의 최단 거리를 저장하는 인접행렬을 정의한다. 자기 자신으로부터 자기 자신에게로 가는 칸은 0으로 설정하고, 다른 칸들은 적당히 큰 값으로 설정한다.
• 노드와 에지 정보를 보면서 위에서 정의한 인접행렬에 에지 가중치 정보를 입력한다.
• 모든 노드를 출발 노드로 하고, 모든 노드를 도착 노드로 하여 모든 경로를 조사하면서 최단 경로를 업데이트 한다.
  • 중간 노드를 설정하는 for문을 노드 개수만큼 돈다.
  • 출발 노드를 설정하는 for문을 노드 개수만큼 돈다.
  • 도착 노드를 설정하는 for문을 노드 개수만큼 돈다.
  • [출발 노드부터 중간 노드까지의 값과 중간 노드부터 도착 노드까지의 값의 합]이 [출발 노드부터 도착 노드까지의 값]보다 작으면 [출발 노드부터 도착 노드까지의 값]을 [출발 노드부터 중간 노드까지의 값과 중간 노드부터 도착 노드까지의 합]으로 업데이트한다.
• 완성된 배열은 모든 노드 간의 최단 거리를 알려준다.

 

4. 코드

public static void floyd(){
    for(int k = 1; k<=N; k++){
        for(int i = 1; i<=N; i++){
            for(int j = 1; j<=N; j++){
                if(adj[i][k]+adj[k][j] < adj[i][j]){
                    adj[i][j] = adj[i][k] + adj[k][j];
                }
            }
        }
    }
}

 

5. 관련 문제

백준 11404

GitHub - Lee-Min-Jung/coding_test_practice

백준 11403

GitHub - Lee-Min-Jung/coding_test_practice

백준1389