플로이드-워셜(Floyd-Warshall) 알고리즘에 대해서 알아보기

플로이드-워셜(Floyd-Warshall) 알고리즘에 대해서 알아보기

플로이드 워셜 알고리즘이란?

-단일 출발점만 가지고 최단 경로를 구하는 다익스트라 알고리즘과 달리 그래프에 존재하는 모든 노드쌍에 대해 최단 경로를 구할 수 있는 알고리즘입니다.(간선이 음의 가중치를 가져도 사용할 수 있음)

-다익스트라 알고리즘의 시간복잡도는 O(V^2)이며 플로이드 워셜 알고리즘은 O(V^3)의 시간복잡도를 가집니다.

다익스트라 알고리즘을 우선순위큐를 이용하면 O((V+E)logV) 시간 복잡도를 가짐.

기존의 다익스트라 알고리즘 설명에 사용됬던 같은 예시로 플로이드 워셜 알고리즘을 설명해보겠습니다.

https://lbdiaryl.tistory.com/164?category=1015060

예시

정점과 간선이 위와 같이 주어진다고 했을 때, 각각의 정점에서 다른 정점으로 가는 비용을 이차원 배열로 나타내면 다음과 같이 나타낼 수 있습니다.

그 다음 노드1을 지나는 모든 경우에 대해 노드A에서 B로 가는 최소비용과 노드A에서 노드1을 거쳐 B로 가는 비용을 비교하여 나온 최솟값으로 배열을 초기화합니다.

노드1을 거쳐가는 경우

이해하기 쉽게 경우의 수를 하나 선택하여 설명해보겠습니다.

기존 노드 2번에서 3을 가는 경우는 바로가는 경우의 비용인 4가 저장되어 있습니다. 다만 여기서 1을 거쳐간다고 할 때 비용은 (2 → 1)+(1 → 3)이 되는데

노드 2번에서 1번으로 가는 경우, 비용은 INF값을 갖기 때문에 4와 INF+3을 비교해서 나온 최종적으로 작은 최솟값인 4가 (2,3)위치에 그대로 남습니다.

이런 식으로 노드5까지 반복하면 다음과 같이 진행됩니다.

노드2를 거쳐가는 경우 노드3을 거쳐가는 경우 노드4를 거쳐가는 경우

노드 4를 거쳐가는 경우를 보면 4번째 행이 다 INF값을 가지기 때문에 바로 넘어가도 되는데

비용을 식으로 표현하면 (A→4)+(4→B)인데 (4→B)가 전부 INF이기 때문입니다.

노드5를 거쳐가는 경우(최종)

노드를 다 거치고 배열의 값의 좌표를 (A,B)라 할 때, A는 출발노드가 되고 B는 도착노드가 되며 (A,B)에 위치한 값은 최단거리가 저장됩니다.

플로이드-워셜 알고리즘을 이용한 코드 구현은 향후 알고리즘 문제를 통해 링크로 걸어놓겠습니다.

+개인적으로 노드가 5개라 25개를 다 구현해야해서 귀찮기도 했고 전부 단방향이라 배열의 변화도 적어 예시로 적절하지 못했던 것같다. 이럴 줄 알았으면 새로 만들걸ㅎㅎ...

from http://lbdiaryl.tistory.com/183 by ccl(A) rewrite - 2021-10-18 18:00:36