플로이드 와샬 (Floyd Warshall)
플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘. 1. 시작점에서 목적지로 가는 경로에 한 정점을 지나갈 때 거리가 더 짧아지면 해당 경로로 갱신한다. 2. 모든 시작점과 모든 목적지 쌍에 대해 1을 반복한다. 당연히 O(n^3)이다. 그냥 코드만 봐도 3중첩 for문이다. 갱신될 때 마다 지나야 하는 k를 저장해두면 되돌아가면서 경로를 찾을 수 있다. #include using namespace std; int INF = 987654321; int PAD = 0; int dist[6][6] = // 그래프 셋팅 //직관적이기 쉽게 index0은 패딩으로 채움 { {PAD,PAD,PAD,PAD,PAD,PAD}, {PAD,0,6,8,INF,2}, {PAD, INF,0,..
