[알고리즘] 플로이드-와샬, Floyd-Warshall

백준 문제를 풀다가 플로이드-와샬 문제를 또 마주쳤다. 몇 번 풀어본적 있는 유형임에도 플로이드 와샬이 뭐더라... 싶더라. 인간은 망각의 동물이구나...

플로이드-와샬 알고리즘

모든 정점에서 모든 정점으로 최단 경로를 구하는 알고리즘
시간 복잡도 O(v^3)
음수 사이클이 없는 그래프에 적용됨
음의 가중치 허용

플로이드-와샬(Floyd Warshall) vs. 다익스트라(Dijkstra)

다익스트라
- 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 (S.S.S.P - Single Source Shortest Path)
- 매번 가장 적은 비용을 가진 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용, 즉 가장 적은 비용을 하나씩 선택하는 로직
- 우선순위 큐 + BFS의 형태
- 시간 복잡도
  - O((V+E)logV): 인접리스트 + 우선순위 큐
  - O(V^2): 인접 행렬
- 음의 가중치를 가지는 그래프에서는 사용불가
플로이드-와샬
- 애초에 거쳐가는 정점을 하나씩 다 설정을 하여 직접 확인하는 방법, 즉 거쳐가는 정점을 기준으로 최단 거리를 구하도록 구성
- 2차원 인접 행렬 사용
- 3중 포문
- 음의 가중치 ok, 음수 사이클 no

음의 가중치란?

음수 사이클은 변의 가중치의 합이 음수를 갖는 사이클이다. 음수 사이클을 구성하는 어떤 꼭짓점 쌍 i,j에 대해서든지 i에서 j로 가는 경로의 길이는 음의 무한으로 내려갈 수 있기 때문에 최단 경로가 존재하지 않는다.

플로이드-와샬 알고리즘의 과정

위와 같은 방향 그래프가 있다고 하자. 정점(노드)이 4개이므로 4X4 인접 행렬이 필요하다.

ROUND 0

0	INF	-2	INF
4	0	3	INF
INF	INF	0	2
INF	-1	INF	0

INF 는 간선이 없음을 의미한다.

ROUND 1 (정점 1을 거칠 경우 고려)

0	INF	-2	INF
4	0	2	INF
INF	INF	0	2
INF	-1	INF	0

정점 1을 거칠 경우를 고려했을 때, 정점 1을 거칠 수 있는 간선이 존재하지 않거나 정점 1을 거치는 게 기존의 것보다 가중치가 클 경우 값이 바뀌지 않는다.

ROUND 2 (정점 2를 거칠 경우 고려)

0	INF	-2	INF
4	0	2	INF
INF	INF	0	2
3	-1	1	0

ROUND 3 (정점 3을 거칠 경우 고려)

0	INF	-2	0
4	0	2	4
INF	INF	0	2
3	-1	1	0

ROUND 4 (정점 4를 거칠 경우 고려)

0	-1	-2	0
4	0	2	4
5	1	0	2
3	-1	1	0

구현 코드

int[][] dist = new int[V + 1][V + 1];

for (int i = 1; i <= V; i++) {
    for (int j = 1; j <= V; j++) {
        dist[i][j] = INF;
    }
}

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

알고리즘 문제 전략

플로이드 와샬 알고리즘은 시간 복잡도가 매우 높기 때문에효율적인 코드 작성이 필요할 때(코테)는V의 크기가 크다(500 이상)면 가급적 피하는 것이 좋다. 입력의 크기가 100 정도만 되어도 백 만번의 연산이 수행되어야 한다. 따라서, 플로이드 알고리즘을 사용하는 경우는 입력의 크기를 주의깊게 살펴보도록 하자.

플로이드 와샬 알고리즘으로 풀어지는 문제는 다익스트라로 풀 수 있다. 모든 정점의 최단 경로를 구할 때, 입력 조건이 충족되었을 경우 플로이드 와샬 알고리즘을 사용하자.

Reference

저작자표시

기록하는 습관