C++에서 Floyd-Warshall 알고리즘을 사용하는 방법

C++에서 Floyd-Warshall 알고리즘을 사용하는 방법

Floyd-Warshall 알고리즘은 방향성 가중치 그래프에서 모든 노드 쌍 사이의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이는 동적 프로그래밍의 아이디어를 채택하고 노드 쌍 사이의 거리 정보를 지속적으로 업데이트하여 최종적으로 최단 경로(즉, 최소 가중치)를 얻습니다.

C++에서는 인접 행렬(Adjacency Matrix)을 사용하여 그래프의 구조를 표현하고, Floyd-Warshall 알고리즘을 통해 최단 경로를 풀 수 있습니다.

인접 행렬은 각 노드 사이의 가중치(거리)를 기록하는 2차원 배열입니다. 두 노드 사이에 직접적인 연결이 없는 경우 더 큰 숫자(예: 무한대)를 사용하여 표현합니다.

다음은 C++에서 Floyd-Warshall 알고리즘을 사용하는 방법을 보여주는 샘플 코드입니다.

#include <iostream>
using namespace std;

const int INF = 1e9; // 无穷大

void floydWarshall(int graph[][4], int n) {
    int dist[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }
  
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最短路径矩阵
    cout << "最短路径矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                cout << "INF" << "    ";
            } else {
                cout << dist[i][j] << "    ";
            }
        }
        cout << endl;
    }
}

int main() {
    int graph[4][4] = { {0, 5, INF, 10},
                        {INF, 0, 3, INF},
                        {INF, INF, 0, 1},
                        {INF, INF, INF, 0} };

    floydWarshall(graph, 4);

    return 0;
}

위 코드에서는 4x4 인접 행렬 그래프를 정의하고 INF를 사용하여 존재하지 않는 가장자리를 나타냅니다. 그런 다음 floydWarshall 함수를 호출하여 그래프와 노드 수를 전달합니다. 함수에서는 dist 2차원 배열을 사용하여 현재 노드 쌍 사이의 최단 경로 정보를 저장합니다.

Floyd-Warshall 알고리즘의 메인 루프에서는 최종 최단 경로 행렬을 얻을 때까지 dist 배열을 지속적으로 업데이트합니다. 마지막으로, 더 쉽게 읽을 수 있도록 INF를 무한대로 대체하여 최단 경로 행렬을 출력합니다.

Floyd-Warshall 알고리즘의 시간 복잡도는 O(n^3)(여기서 n은 노드 수)이므로 대규모 그래프의 경우 알고리즘이 느리게 실행될 수 있습니다.

이 기사가 C++의 Floyd-Warshall 알고리즘을 이해하고 사용하는 데 도움이 되기를 바랍니다.

위 내용은 C++에서 Floyd-Warshall 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!