[알고리즘] 플로이드-워셜(Floyd-Warshall)

[  플로이드-워셜(Floyd-Warshall)  ]

---

그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다

 

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.

• 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.

다익스트라(Dijkstra) 알고리즘

다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다
특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다
음의 간선을 포함할 수 없지만 현실 세계에서는 음의 간선이 존재하지 않기 때문에 현실 세계에 사용하기 매우 적합하다
하나의 최단거리를 구할 때 그 이전까지 구했던 최단  거리의 정보를 그대로 사용한다

 

 

[  시간 복잡도  ]

---

노드의 개수가 𝑁개일 때 알고리즘상으로 𝑁번의 단계를 수행한다

각 단계마다 O(N²) 의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다

따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N³) 이다

 

 

[  동작 과정  ]

---

초기 상태

그래프를 준비하고 최단 거리 테이블을 초기화한다

 

 

1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

 

 

2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

 

 

3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

 

 

4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다

 

출처 : https://freedeveloper.tistory.com/277?category=888096

 

 

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

---

import java.util.*;

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M)
    // 노드의 개수는 최대 500개라고 가정
    public static int n, m;
    // 2차원 배열(그래프 표현)를 만들기
    public static int[][] graph = new int[501][501];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        // 최단 거리 테이블을 모두 무한으로 초기화
        for (int i = 0; i < 501; i++) {
            Arrays.fill(graph[i], INF);
        }

        // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                if (a == b) graph[a][b] = 0;
            }
        }

        // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
        for (int i = 0; i < m; i++) {
            // A에서 B로 가는 비용은 C라고 설정
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph[a][b] = c;
        }

        // 점화식에 따라 플로이드 워셜 알고리즘을 수행
        for (int k = 1; k <= n; k++) {
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++) {
                    graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
                }
            }
        }

        // 수행된 결과를 출력
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
                if (graph[a][b] == INF) {
                    System.out.print("INFINITY ");
                }
                // 도달할 수 있는 경우 거리를 출력
                else {
                    System.out.print(graph[a][b] + " ");
                }
            }
            System.out.println();
        }
    }
}

 

 

 

 

참조

https://freedeveloper.tistory.com/277?category=888096