주의할 점.

• 시간복잡도는 n의 세제곱이므로, 정점과 간선이 많다면 ,
  다익스트라를 사용하는 편이 좋음.

😘정의 그리고 점화식

: dist(a,b) = min(dist(a,b) , dist(a,k) + dist(k,b));

• a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사하는 알고리즘

• 플로이드 와샬은 모든 정점간의 최단 거리를 구함.

• 다익스트라는 하나의 정점을 기준으로 다른 모든 정점까지의 최소거리를 구하는 것이다.

사용

• 이차원 배열을 사용하자.
• 초기값은 어마어마 하게 큰값으로 , 팁으로는 비용 * 모든 간선의 값이다.
• 자기 자신의 값은 0이겠지
• dp[i][j] : i정점에서 j정점까지의 비용을 나타낸다.
• 경유하는 점 k에 대해 생각할 수 있다.

  dp[1][8] : 1번 정점에서 8번까지의 가는데의 비용을 나타내는데,
  경유하는 k점이 만약에 더 작게 된다면
  값을 갱신해야 한다.

소스코드

for(int k = 0; k < n; k++)
{
	for(int i = 0; i < n; i++)
    {
    	for(int j = 0; j < n; j++)
        {
        	dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]);
        }
    }
}