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

• 모든 정점에서 모든정점으로의 최단경로를 구할때 사용
• 경유지(거쳐가는 정점)를 기준으로 최단거리를 구함
• 다이나믹 프로그래밍(큰 문제를 작은 문제들로 나눠서 해결)을 보여줌

자료출처:https://blog.naver.com/ndb796/221234427842

 

 

 

아래의 표는 위그래프를 기준으로 출발지에서 목적지까지의 최소 비용을 구한 것이다, 화살표가 목적지로 정방향으로 가리키지 않거나, 중간에 경유지를 거쳐야 하는 경우(예 2 -> 4)들은 무한(값이 있긴한데 정확히 얼마나 되는지 몰라서 무수히 많은 값)으로 추정한다

따라서 위 그래프를 읽으려면, 1에서 2까지 가는 최소 비용은 5 이고

1에서 3까지 가는 비용은 화살표가 1->3 으로 나와있지 않으므로 무한이고

1에서 1 또는 2에서 2 등등 자기 자신을 향하는 경우 비용이 들지 않으므로 모두 0이다 

 

 

 

플로이드 와샬 알고리즘은 모든 정점을 각각 경유지(거쳐가는 정점)로 봤을때 나올 수 있는 최소비용들을 구해서

표를 갱신해 나가는 것이다

이때 이공식이 사용된다

 

X에서 Y로가는 최소비용 vs X에서 '경유지'로 가는 비용 + 경유지 에서 Y로 가는 비용

 

즉, 거쳐가는 정점을 1번부터 시작해서 4번까지 바꿔가면서, 각각의 경유지(거쳐가는 정점)마다

자기 자신으로 가는 경우는 제외

출발지 또는 목적지가 경유지인 경우도 제외(출발지가 목적지가 경유지인 경우, 경유하는게 아니므로)

한뒤 최소비용을 위의 공식에 맞춰서 갱신해 나가는 것이다 일단 1번부터 거쳐가는 정점이라고 한다면

최소비용을 갱신해야될 부분은 아래의 노란부분과 같다

위의 표의 노란부분은 

자기 자신으로 가는 경우는 제외

출발지 또는 목적지가 경유지인 경우도 제외(출발지가 목적지가 경유지인 경우, 경유하는게 아니므로)

한 나머지들이며 갱신해야될 부분이다

 

 

2->3 으로 가는 최소비용은 9인데 

경유지는 1이다

X에서 Y로가는 최소비용 vs X에서 '경유지'로 가는 비용 +'경유지'  에서 Y로 가는 비용

 

위의 공식을 대입 시키면

 

2에서 3으로 가는 최소비용 vs 2에서 1로 가는 비용 + 1에서 3으로 가는 비용

 

이 된다, 그대로 표를 보고 대입하면

 

9 vs 7 + 무한

 

이 된다 여기서 7+ 무한은 값이 확실하지 않으므로 결국 무한으로 추정하고

9와 비교했을때 9가 더 적다고 판단하여 9를 내버려둔다

 

 

이런식으로 갱신해 나가면 아래와 같이 된다

여기서 3->2로 가는 값이 무한에서 7로 바뀐걸 알 수 있다

3 -> 2 로 가는 비용 > (3 -> 1) + (1 -> 2)

무한 > 2 + 5

이므로 2+5 가 무한보다 적으므로, 즉 7로 바뀌었다

 

그뒤 1을 거치는 표를 기준으로 경유지를 1에서 2로 바꾸고 다시 갱신해준다

아래와 같을 것이다

 

이런식으로 계속 경유지를 바꿔가며 표를 갱신하면된다

 

경유지가 마지막 정점인 4인경우 표가 다 완성된다

 

 

 

코드

#include <iostream>

int number = 4;
int INF = 100000000;

// 자료 배열을 초기화
int a[4][4] =
{
	{0, 5, INF, 8},
	{7, 0,	9, INF},
	{2, INF, 0, 4},
	{INF, INF, 3, 0}
};


void floydWarshall()
{
	int oldCost = 0;
	int newCost = 0;
	
	// 결과 그래프를 초기화
	//X에서 Y로가는 최소비용 VS X에서 '거쳐가는노드'로 가는 비용 + 노드1 에서 Y로 가는 비용
	for (int stopover = 0; stopover < number; stopover++) //stopover : 경유지, 거쳐가는 노드
	{
		for (int start = 0; start < number; start++)
		{
			for (int goal = 0; goal < number; goal++)
			{
				if (stopover < number&& start != goal && start != stopover && goal != stopover)
				{
					oldCost = a[start][goal]; //X에서 Y로가는 최소비용

					//X에서 '거쳐가는노드'로 가는 비용 + 노드1 에서 Y로 가는 비용
					newCost = a[start][stopover] + a[stopover][goal]; 
					
					//둘중에 더 적은 비용을 넣기
					a[start][goal] = oldCost > newCost ? newCost : oldCost; 
				}
			}
		}
	}
}

void PrintGraph(int (*_a)[4])
{
	for (int start = 0; start < number; start++)
	{
		for (int goal = 0; goal < number; goal++)
		{
			if (a[start][goal] == INF)
			{
				printf("INF ");
			}
			else
			{
				printf("%d ", a[start][goal]);
			}
		}
		printf("\n");
	}
	printf("\n\n");
}

int main()
{
	PrintGraph(a);

	floydWarshall();
	printf("after FloydWarshall \n");
	PrintGraph(a);
	
	return 0;
}

n번 만큼의 루프 연산이 삼겹으로 들어가므로 O(n³) 만큼의 시간복잡도를 가진다

실행결과

위에서 봤던 최종 결과 표와 일치한 결과를 볼 수 있다.