플로이드 워셜 C++코드

#include <iostream>
#include <vector>
#include <algorithm> // std::min 사용

using namespace std; // std 네임스페이스를 전역적으로 사용

const int INF = 1e9; // 무한대를 의미하는 큰 값

void floydWarshall(vector<vector<int>>& dist, int V) {
    // 모든 정점 쌍 (i, j)에 대해 i에서 j로의 최단 경로 계산
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][k] < INF && dist[k][j] < INF) { // 두 값이 모두 유효한 경우에만 갱신
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

int main() {
    int V; // 정점의 개수
    cout << "정점의 개수를 입력하세요: ";
    cin >> V;

    // 거리 행렬 초기화
    vector<vector<int>> dist(V, vector<int>(V));

    cout << "거리 행렬을 입력하세요 (직접 연결되지 않은 경우 " << INF << "을 입력하세요):\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cin >> dist[i][j];
        }
    }

    // 플로이드-워셜 알고리즘 수행
    floydWarshall(dist, V);

    // 결과 출력
    cout << "최단 거리 행렬:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF)
                cout << "INF ";
            else
                cout << dist[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}