📖 모든 쌍의 최단 경로 찾기

---

• 한 노드에서 다른 노드로 가는 간선이 없는 경우 가장 빨리 갈 수 있는 길 찾는 문제
• 가중치 포함, 방향성 그래프에서 최단 경로 찾기
• 최적화 문제
  • 주어진 문제에 대해 하나 이상의 많은 해답이 존재할 때, 이 가운데에서 가장 최적인 해답 찾아야하는 문제

💬 DP 접근 방법

---

• 다익스트라(Dijkstra)의 최단 경로 알고리즘 수행
  • 이 때 시간 복잡도 : O(n^3)
• Warshall은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 DP 알고리즘 제안
• Floyd는 이를 변형해 모든 쌍 최단 경로 찾는 알고리즘 고안
• 시간 복잡도 : O(n^3)
  • 다익스트라와 시간 복잡도는 같지만 코드가 간략해짐
• 인접 행렬 이용
  • 초기 인접 행렬의 값은 자기 자신에서 자기 자신으로 가는 경우(=0)를 제외하고는 다른 노드로 갈 수 있는 방법이 없으므로 모두 매우 큰값으로 초기화

💬 알고리즘 구현

---

• 위 그림과 무관

int INF = Integer.MAX_VALUE;		
int[][] dist = {{0,7,INF,INF,3,10,INF}
				,{7,0,4,10,2,6,INF}
				,{INF,4,0,2,INF,INF,INF}
				,{INF,10,2,0,11,9,4}
				,{3,2,INF,11,0,INF,5}
				,{10,6,INF,9,INF,0,INF}
				,{INF,INF,INF,4,5,INF,0}};
	
// 플로이드 워셜 알고리즘
// 노드를 1개부터 N개까지 거쳐가는 경우
for (int k = 0; k < 7; k++) {
	// k노드를 거쳐 노드 i에서 j로 가는 경우.
	for (int i = 0; i < 7; i++) {
		for (int j = 0; j < 7; j++) {
			// k번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
			// 또는 연결이 안되어있던 경우(INF) 연결 비용 갱신
			dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
}