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

플로이드 워셜이란?

그래프 상에 각각의 노드에서 출발하여, 특정 노드까지의 최단거리를 모두 구해주는 알고리즘이다.

+ 다익스트라는 한 지점에서 모든 지점까지의 최단거리를 구해주지만, 플로이드 워셜은 모든 지점에서 모든 지점까지의 최단거리를 구할 수 있다.

 

특징

세개의 중첩 반복문을 사용하고, O(v^3)의 시간 복잡도를 가진다.

 

구하는 방법과 원리

보통 이 알고리즘을 사용하는 문제는, 한 지점에서 다른 지점까지의 거리를 모두 알려준다.

주어진 정보를 활용하여 최단거리를 구해야 하는데, 이때 a지점에서 b지점까지의 거리와, a지점에서k + b지점에서k까지의 거리를 비교하여 더 적은 값을 최단거리로 잡는다.

이 부분에 대한 코드만 보면 이렇다.

for k in range(1, n+1):

    for a in range(1, n+1):

        for b in range(1, n+1):

            data[a][b] = miin(data[a][b], data[a][k]+data[b][k])

-> 이렇게 하면 a-b까지의 거리와 a-k + k-b와의 모든 경우의 수를 고려해준 것이 된다.

 

 

* 여기서 의문점이 생겼었다.

왜 data[a][b] = miin(data[a][b], data[a][k]+data[b][k]) 이게 모든 최단 거리를 고려해 준 것이지?!

의문점이 생긴 이유는 다음과 같다.

- 아니! 한 점에서 k점을 거치고 간 것만 비교해주면 모든 것을 고려해 준 것인가!? 막 다른데 더 들렀다가 온게 최단거리일 수 있지 않나??😥

 

하지만 직접 그려본 후, 이 생각이 틀린 것임을 알게 되었다.

a-b로 바로 가는 것 보다, 다른 지점을 거쳐서 가는 것이 더 최단 거리일 수는 있다. 하지만 이 이외에는 더 짧은 것이 나올 수가 없다. 예를 들어, a-k k-b에서 이 사이에 다른 곳을 거친다면, 무조건 안거친 것이 더 짧다.

그렇다고 어찌저찌 더 짧은 거리가 있지 않을까,,,? 하는 생각이 문득 들어도, a-k k-b는 이러한 모든 경우를 포함해준다.

 

막상 그려보니 알겠긴 한데,,, 뭔가 왜 이렇게 되는지는 명쾌하게 와닿지는 않는다..

신기하구먼,,,

 

이거 이해하는데 삼일이나 걸리다니,,, 하 ㅠㅠ 갈 길이 멀다