플로이드와샬 알고리즘(FloydWarShall)

안녕하세요. 옆집컴공생입니다. 오늘은 플로이드와샬 알고리즘(Floydwarshall) 에 대해 알아볼게요. 저번에 포스팅했던 다익스트라 알고리즘과 비슷한 부분이 굉장히 많은 알고리즘입니다. 혹시 다익스트라가 뭔지 모르시는 분은 아래 포스팅을 확인해주세요.

 

https://com24everyday.tistory.com/137

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

 

다익스트라 알고리즘은 '한 정점에서부터 다른 모든 노드를 최소 비용으로 가는 방법' 이었습니다.

그럼 플로이드와샬은? 

'모든 정점에서부터 모든 노드를  최소 비용으로 가는 방법' 입니다. 

 

개념 자체는 약간 확장된 형태라고 볼 수 있겠네요. 

 

플로이드와샬은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 점이 중요합니다. 또한 다익스트라와 마찬가지로 다이나믹 프로그래밍 기술을 사용합니다. 

 

▶핵심은 '거쳐가는 정점을 기준으로 최단거리 구함' 입니다. 

 

 

---

위와 같은 그래프를 통해 플로이드와샬 알고리즘 진행에 대해 알아봅시다. 플로이드와샬 알고리즘에서는 2차원 배열을 통해 노드 간에 비용을 표현합니다. 

 

행은 가로, 열은 세로입니다.(늘 헷갈립니다ㅠㅠ) 면 1행 2열인 3은 노드 1에서 2로 가는데 드는 비용입니다.

갈 수 없는 노드는 무한으로 표현했습니다. 플로이드 와샬 알고리즘은 다이나믹 프로그래밍과 달리 그냥 모든 노드를 다 검사해버립니다. 굳이 가장 짧은 위치에 노드부터 시작할 필요가 없습니다. 노드 1을 거쳐가는 경우부터 알아보겠습니다. 

 

 

1. 노드 1을 거쳐가는 경우

 

노드마다 갱신시켜야하는 위치에 대해 먼저 알아보겠습니다.

행 -> 열, 이 노드간의 이동이라고 했습니다. 우리가 갱신해야할건 '이 노드를 거침으로서 값이 변하나?' 에 대한 겁니다. 그러면 노드 1이 2로 이동하는 부분을 갱신해야할 필요가 있을까요.

 

그럼 식은 ' 1 -> 2' 에서 '1 -> 1 - >2' 이렇게 됩니다. 의미가 없죠?

 

우리가 봐야하는 건 '2 -> 3' 의 비용보다 ' 2 -> 1 -> 3' 이 나은지에 대한 겁니다. 그럼으로 노드 1은 1행 부분과 1열 부분 그리고 대각선 부분을 갱신해야할 필요가 없습니다.(애초에 대각선은 ' 1->1'과 같은 자기 자신에 대한 이동이기 때문에 값이 다 0입니다.) 

 

아래의 색칠된 부분이 갱신해야 할 부분입니다.

 

여기서 이제 선택한 노드 1 를 거쳐서 가는 부분을 비교하는겁니다. 

 

X -> Y 로 가는 최소 비용   vs  X -> 노드1 로 가는 비용 + 노드 1에서 Y로 가는 비용

 

즉 노드 1로 거쳐가서 더 빠르다면 갱신을 해주는 겁니다. 즉 D[2,3] 의 값은 D[2,3] 과 (D[2,1] + D[2,2]) 의 값을 비교해서 갱신해주는거죠. 그러므로 그래프를 잘 따라가서 갱신을 해주면 다음과 같은 표가 구성됩니다. 

(제가 그래프를 잘못 그려서 그런지 갱신된게 없네요)

 

2. 노드 2를 거쳐가게 해보겠습니다. 다음과 같은 위치에 갱신이 필요합니다.

갱신을 하면 다음과 같아집니다.

 

이렇게 노드 3,과 4를 거치는 과정을 진행하면 최종적으로 다음과 같은 결과가 나옵니다.

 

이에 대한 소스코드는 다음과 같습니다. 

 

결과값

보면 삼중 for문을 쓰고 있습니다. 그러므로 시간복잡도는 O(N^3) 으로 엄청 오래 걸립니다. 노드가 조금만 많아도 컴퓨터가 먹통이 될거 같습니다. 1,000 면 계산 시간이 1,000,000,000,  백억번이 되어버리네요.

 

오늘은 '모든 정점에서 다른 모든 정점으로 갈때의 최소 비용 구하기' 를 배워보았습니다. 수고하셨습니다!

 

 

아래의 백준 문제를 통해 플로이드와샬을 연습하실 수 있습니다. 

https://www.acmicpc.net/problem/11404

11404번: 플로이드