플로이드 워셜 알고리즘 (1) - 동작 원리

샤핑

 

 

이번 시간에는 플로이드 워셜 알고리즘의 동작 원리를 살펴보겠습니다.

 

플로이드 워셜(Floyd-Warshall) 알고리즘

- 그래프에서 모든 노드의 최단 거리를 구하는 알고리즘입니다.

- 각 노드마다 가장 짧은 거리를 구한다고 이해하면 됩니다. 예를 들어, 노드 A, B, C가 있으면, A-B, A-C, B-C, 이렇게 가장 짧은 거리를 하나도 빠짐 없이 모두 구하는 것입니다. 이때, 출발지, 도착지, 경유지를 각각 설정합니다. 자세한 것은 아래에서 설명하겠습니다.

 

 

 

위의 그래프로 알고리즘의 원리를 살펴보겠습니다.

 

 

 

우선, 출발지, 도착지, 경유지를 위와 같이 설정하고, 도착지 -> 출발지 -> 경유지 순으로 바꿔나가겠습니다. 플로이드 아샬은 모든 노드에 모든 경우의 수로 출발지, 도착지, 경유지를 각각 설정합니다. 이때, 경유지를 거쳐갔을 때의 비용이 더 작다면, 이것을 최단 경로로 설정합니다. 예를 들어, A-C의 최단 경로를 구하는 상황에서, A-C가 8이고 A-B-C가 5이면, B를 거쳤을 때의 비용이 더 작으므로, A-C의 최단 경로는 5가 되는 것입니다. 구체적인 원리는 그림을 보면서 살펴보겠습니다.

 

 

 

경유지: 1

출발지: 2

도착지: 3

 

출발지-도착지 : unknown(∞)

출발지-경유지-도착지 : 3+6=9

 

경유지를 거쳤을 때의 비용이 더 작습니다. 따라서, 최단 경로를 9로 설정합니다.

 

 

 

경유지: 1

출발지: 2

도착지: 4 (도착지 변경)

 

출발지-도착지 : 5

출발지-경유지-도착지 : unknown(∞)

 

바로 직행했을 때의 비용이 더 작습니다. 따라서, 최단 경로를 바꾸지 않습니다.

 

 

 

경유지: 1

출발지: 2

도착지: 5

 

출발지-도착지 : unknown(∞)

출발지-경유지-도착지 : unknown(∞)

 

두 비용이 서로 같습니다. 따라서, 최단 경로를 바꾸지 않습니다.

 

 

 

경유지: 1

출발지: 3 (출발지 변경)

도착지: 2

 

출발지-도착지 : 9 ('노드2-노드3'의 비용을 9로 설정했으므로)

출발지-경유지-도착지 : 6+3=9

 

두 비용이 서로 같습니다. 따라서, 최단 경로를 바꾸지 않습니다.

 

 

 

경유지: 1

출발지: 3

도착지: 4

 

출발지-도착지 : 8

출발지-경유지-도착지 : unknown(∞)

 

바로 직행했을 때의 비용이 더 작습니다. 따라서, 최단 경로를 바꾸지 않습니다.

 

 

 

경유지: 1

출발지: 3

도착지: 5

 

출발지-도착지 : 1

출발지-경유지-도착지 : unknown(∞)

 

바로 직행했을 때의 비용이 더 작습니다. 따라서, 최단 경로를 바꾸지 않습니다.

 

 

 

...(중략)...

 

경유지: 2 (경유지 변경)

출발지: 1

도착지: 3

 

...(중략)...

 

이렇게 모든 경우의 수로 출발지, 도착지, 경유지를 각각 설정해서 최단 경로를 구합니다.

 

 

 

이렇게 하면 최종적으로 위의 표가 만들어집니다. 이것은 출발지-도착지의 각 최단 경로를 의미합니다. 가령, '노드2-노드5'의 최단 경로는 7이고, '노드2-노드3'의 최단 경로는 8입니다. (빨강색 표시 참고) 그리고 그래프가 양쪽으로 이동할 수 있는 루트로만 구성되어 있으므로 표가 대칭을 이룬 것을 볼 수 있습니다.

 

소스 코드: https://sharpcoder.tistory.com/319

 

 

728x90