모든 쌍 간의 최단 거리 구하기

그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[ ][ ]를 계산한다. 이 배열의 원소 dist[u][v]는 정점 u에서 v로 가는 최단 거리를 나타낸다.

이론

정점 a에서 b를 갈 때 거칠 수 있는 정점들을 경유점 x라고 하면

a에서 b 가는 최단 경로는 a→b 와 a→x + x→b 중 짧은 거.

이걸 재귀적으로 써서 동적 계획법으로 푸는 것이다.

// 정점의 개수
int V;
//그래프의 인접 행렬 표현
// adj[u][v] = u에서 v로 가는 간선의 가중치. 간선이 없으면 아주 큰 값을 넣는다.
int adj[MAX_V][MAX_V];
int C[MAX_V][MAX_V][MAX_V];

void AllPairShortestPath1()
{
	// C[0]을 초기화
	for (int i = 0; i < V; ++i)
		for (int j = 0; j < V; ++j)
		{
			if (i != j)
				C[0][i][j] = min(adj[i][j], adj[i][0] + adj[0][j]);
			else
				C[0][i][j] = 0;
		}
		// C[k-1]이 있으면 C[k]를 계산할 수 있다.
		for (int k = 1; k < V; ++k)
			for (int i = 0; i < V; ++i)
				for (int j = 0; j < V; ++j)
					C[k][i][j] = min(C[k-1][i][j], C[k-1][i][k] + C[k-1][k][j]);

이 코드에서 C_k(u, v)의 값은 0번 정점부터 k번 정점까지만을 경유점으로 썼을 때 u에서 v까지 가는 최단 경로의 길이이며, C[k][u][v]에 저장된다. 따라서 함수의 종료 후에 u에서 v로 가는 최단 거리를 알려면 C[V-1][u][v]를 보면 된다.

인접 행렬 표현에서 두 정점 사이에 간선이 없는 경우 아주 큰 값을 넣어야 한다는 것을 주의해야 한다.

존재하는 어떤 경로의 길이보다도 커야 한다. 그리고 만약에 C[V-1][u][v]가 아주 큰 값 이상이라면 경로가 존재하지 않음을 알 수 있다.

// C[k-1][i][k] + C[k-1][k][j] 가 있기 때문에 한 번은 더해도 되는 INF 값으로 해야 할 듯! (~0U>>2)

시간 복잡도 및 공간 복잡도

모든 정점에 대해서 다익스트라, 음수 간선이 있으면 벨만-포드 쓰면 되는 거 아닌가?

얘가 시간 복잡도 O(|V|^3) 으로 더 빠르다고 함. (반복문 내부도 단순하고).