플로이드-워셜 알고리즘

- 플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘으로 시간복잡도는 O(V^3)이다.

- 특정 노드 사이의 간선이 없을 경우 INF로 표시하여 인접행렬을 만들 수 있다. ROUND를 반복하면서 인접행렬을 그린다. 노드간의 최단 거리로 인접행렬을 완성한다.

- 소스코드로 구현할 경우 3개의 FOR문으로 만들 수 있다.
먼저 초기 인접 행렬의 값을 사용해 노드 사이의 최단 거리 배열을 초기화한다.

for(int i = 1; i<=n; i++){
    for(int j =1; j<=n; j++){
        if (i == j) dist[i][j] = 0;
        else if (adj[i][j]) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

이후 중간 노드가 될 노드 번호를 FOR문의 가장 바깥 변수로 잡고, 내부 이중 for문의 변수들을 통해 각 노드별 거리를 살펴보면서 k를 중간노드로 삼을때와 아닐때의 값을 비교한 후 더 작은 값으로 업데이트한다.

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