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

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

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

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

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

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

#include  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 중국어 웹사이트의 기타 관련 기사를 참조하세요!