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

플로이드 워셜

개념

정점 i에서 j까지 가는 최단 경로를 구할 때 중간 정점을 거쳐서 갈 수 있으면 거쳐서 가는 게 더 빠른지 확인하면서 최단 경로를 구하는 알고리즘

임의의 경로 p에 중간 정점 k가 존재하면 k를 거쳐 가는 경로와 비교하여 더 작은 값으로 갱신하고, 중간 정점이 존재하지 않으면 아무 것도 하지 않는다.

여기서 알 수 있는 특징은 거쳐갈 중간 정점이 여러 개가 될 수 있는데, 중간 정점 개수가 늘어날 수록 경로가 더 다양해지고 더 짧은 경로를 발견할 수 있는 확률이 늘어난다는 것이다.

그리고 중간 정점 후보가 {1, 2, 3, ..., k} 이렇게 존재한다면 중간 정점을 단계적으로 확장해나가며 점점 더 정교한 최단 경로를 계산해나간다.

즉 경로를 점점 확장해가면서 가능한 모든 조합을 다 비교하고 있다.

다익스트라처럼 최단 경로를 그리디하게 확정하는 것과는 다른 개념이다.

점화식은 다음과 같다.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점까지의 최단거리를 모두 구할 수 있는 알고리즘

음의 가중치가 사이클에 포함되지만 않는다면 존재해도 상관 없음

 

다익스트라와는 다르게 음의 가중치가 있어도 괜찮은 이유

다익스트라가 음의 가중치가 있으면 안 되는 이유는

특정 정점에서 시작하여 그리디하게 지금까지 선택한 경로가 최단거리라고 확정지으면서 선택하다가

나중에 음의 간선이 발견되면 지금까지 선택한 경로가 최단거리가 아니게 되기 때문이었다.

 

그런데 플로이드워셜에서는 그리디하게 선택해나가는 게 아니라 그래프에서 나올 수 있는 모든 경로들을 하나도 빠짐없이 다 검사하므로 음의 가중치가 있어도 최단경로를 찾는 게 가능하다.

 

즉 다익스트라는 '지금까지 확정한 경로가 최선'이라는 가정 하에 동작 -> 이 가정은 음의 간선이 있으면 깨짐

플로이드 워셜은 모든 경로를 다 체크하고 비교하기 때문에 경로가 어떻게 생기든 계산 결과로 가장 짧은 걸 찾아내면 됨

 

사이클이 있어도 괜찮은 이유

사이클의 문제점을 직관적으로 생각해보면 쉽다.

최단 경로를 찾는 데 있어 그 사이클을 도는 게 더 짧아질 수 있으면 문제고 아니면 아무 상관 없다.

 

다익스트라는 사이클이 있어도 가중치가 다 양수이면 상관 없다.

사이클을 지나가는 경로가 최단 경로보다 더 짧을 수 없기 때문에 큐에 넣기 전에 확인하는 조건문에 의해 사이클이 자동으로 무시된다.

 

플로이드 워셜 또한 사이클이 있어도 가중치가 다 양수이면 상관 없다.

경로를 구성하는 모든 가능한 정점 k를 거쳐가며 비교하기 때문에 더 짧은 경로가 있으면 그 경로가 선택되기 때문이다.

 

반면 다익스트라, 플로이드 워셜 모두 사이클 가중치가 음수이면 안 된다.

둘 다 최단 거리를 찾기 위해 경로를 계속 갱신하는 알고리즘인데 음의 사이클이 있으면 최단 거리가 무한히 갱신될 수 있기 때문이다.

 

특징

dp를 이용한 알고리즘

인접 행렬을 이용하여 각 노드간 최소 비용을 계산

모든 노드에서 모든 노드로 가는 최소 비용을 단계적으로 갱신하면서 진행됨

 

단계적으로 갱신한다는 것은 노드에서 노드로 가는 간선의 개수가 0개에서 N개(총 노드 개수만큼 간선을 선택)까지 몇 개의 간선을 거쳐서 해당 노드로 가는지 모두 고려한다는 의미

 

초기화

- 자기 자신으로 가는 경로는 0 (dp[i][j] = 0)

- 간선이 없는 경로는 무한대

- 주어진 간선 정보를 기반으로 초기 거리 행렬 설정

dp[i][j] = i부터 j까지의 최소 비용

 

구현

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

i에서 j로 가는 최단거리는 직접 가는 거리와 어떤 중간 노드 k를 거쳐서 가는 거리 중 더 짧은 쪽이다.

이 과정을 모든 노드 k에 대해 반복하면서 k를 중간 경유지로 사용하는 경우를 계속 고려해나감

for k in range(V):        # 중간 노드
    for i in range(V):    # 출발 노드
        for j in range(V):# 도착 노드
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

 

다익스트라와 비교

다익스트라

• 한 정점에서 출발하여 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 가장 적은 비용을 하나씩 선택하기
• 단일출발점 + 그리디 + 우선순위큐 기반

플로이드 워셜

• 모든 정점에서 출발하여 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 3중 for문을 돌면서 dp를 완성해나감
• 하위 문제의 해를 이용해 상위 문제를 푸는 전형적인 dp 패턴
• 각 단계에서 중간 경유지 k를 추가함으로써 점점 더 최적화된 해를 만들어내는 구조
• 시간 복잡도는 항상 O(V^3)
• 완전 탐색으로 모든 경로를 일일이 다 보는 방법은 비효율적, 반면 플로이드-워셜은 경로 간 거리 정보를 누적하며 최단 거리를 누적하므로 완탐보다 효율적인 방식
• 모든 출발점 + dp 기반

이행적 폐쇄 (transitive clousure)

이행성이란 a->b, b->c면 a->c도 성립한다는 성질

 

이행적 폐쇄란 이행성을 만족하도록 최소한의 경로를 추가한 관계

즉 i->k, k->j로 도달 가능한지 확인하여 i->j로의 도달 가능성을 표시

도달 가능하면 1, 도달 불가능하면 0으로 표시함

 

아래와 같이 플로이드 워셜을 사용하여 거리를 계산하는 대신

경로 존재 여부만 확인해서 0 또는 1로 표시하면 이행적 폐쇄를 구현할 수 있음

if(dist[i][k]==1 && dist[k][j]==1)
	dist[i][j] = 1;
else
	dist[i][j] = 0;