Algorithm/플로이드

[Algo] 플로이드 c++

* 언제 사용?모든 정점간의 최단거리를 구할때 사용시간복잡도 : O(n^3), n=100일때가 정해. n=1000일때도 비빌수는 있음.인접리스트보다는 행렬이 유리!다익스트라 : 한시작점에서 다른 모든 정점의로의 최단거리 구하는 알고리즘 / O(V ElgE) * 의사코드3중 for문을 돌면서정점 k를 하나씩 추가해가면서 이걸 거쳐서 가는게 싼지 탐색k의 for문은 맨 밖에 둬야함에 주의.연산이 대입보다 빠르기때문에, min보다는 if(d[i][j] > d[i][k]+d[k][j]) 인경우 대입하도록 바꾸면 n=1000도 비빌수있음. * 전체코드#include using namespace std;typedef long long ll;int INF = 0x3f3f3f3f;int d[105][105]; //i에..