C++에는 코드 조각이나 예상 값으로 정의되는 매크로가 있으며 사용자가 필요할 때마다 재사용됩니다. Floyd-Walshall 알고리즘은 주어진 가중치 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 프로세스입니다. 알고리즘은 최소 가중치 그래프를 찾기 위해 동적 프로그래밍 접근 방식을 따릅니다.
프로이트-월셔 알고리즘의 의미를 다이어그램을 통해 이해해 봅시다 -
꼭지점 1을 소스로 하고 꼭지점 4을 목적지로 하여 둘 사이의 최단 경로를 찾습니다.
대상 정점 4에 연결될 수 있는 경로가 두 개 있다는 것을 확인했습니다.
1 -> 4 – 가장자리의 무게는 5
1 -> 8 -> 3 -> 4 – 가장자리 가중치(1+2+1)는 4입니다.
주어진 그래프 I에서 두 꼭지점을 연결하는 최소 모서리를 볼 수 있습니다. 따라서 정점 8에서 정점 3까지의 경로는 정점 1을 정점 4으로 연결하고 가장자리는 4입니다. 반면에 정점 1에서 정점 4까지 방향이 있는 가장자리가 있고 가장자리의 가중치는 5입니다.
이제 4과 5이라는 두 가지 가중치를 비교합니다. 따라서 여기서 4는 Floyd Warshall 알고리즘에 따라 계산된 그래프의 최소 가중치입니다.
이 기사에서는 Floyd Warshall 알고리즘을 사용하여 주어진 두 노드 사이의 최단 경로를 찾습니다.
다음 구문은 프로그램에서 사용됩니다 -
으아악data_type[][] - 사용자가 언급한 데이터 유형입니다. 첫 번째 배열은 행을 나타내고 두 번째 배열은 열을 나타냅니다. 따라서 이는 2차원 배열을 나타냅니다.
array_name - 배열에 지정된 이름입니다.
헤더 파일 'iostream'으로 프로그램을 시작하고 매크로 위치를 'INF'(무한대)로 정의합니다. 나중에 2D 배열 행렬과 if-else 문을 만족하게 되기 때문입니다.
다음으로 'printPath'라는 전역 함수 정의를 만들고 'parent[]', 'i' 및 'j'라는 세 가지 매개 변수를 허용하여 경로가 존재하는지 확인합니다.
그런 다음 주 함수를 시작하고 '4' 값을 정점 수를 나타내는 변수 'V'에 저장합니다. 둘째, 인접 행렬 형태로 값을 변수 'dist[V][V]'에 저장합니다. 우리가 알고 있듯이 dist[i][j]는 인접 행렬을 저장하여 'i'에서 'j'까지의 가장자리 가중치를 정의하는 2D 행렬을 나타냅니다.
다음으로 변수 'parent'에 대한 2D 배열을 크기 [V][V]로 초기화합니다.
이 변수에서 우리는 정점 'i' 및 'j' w.r.t 'parent[i][j]'.
의 각 쌍을 표시하는 데 사용합니다.두 개의 중첩된 for 루프를 사용하여 최단 경로를 찾을 수 있습니다. 첫 번째 for 루프는 행렬의 행을 반복합니다. 그런 다음 두 번째 for 루프를 통해 행렬의 열을 반복한 후 if-else 문을 사용하여 다음 조건을 확인합니다. -
If (dist[i][j] != INF && i != j) { parent[i][j] = i;}
의 중국어 번역은 다음과 같습니다. parent[i][j] = i;}if 문에서 'and' (&&) 연산자를 사용하여 두 조건이 모두 충족되면 'i'가 'parent[i][j]'에 저장되어 다음을 확인합니다. 경로가 존재합니다.
기타{ parent[i][j] = -1;}
의 중국어 번역은 다음과 같습니다. parent[i][j] = -1;}else 문에서는 "-1"을 "parent[i][j]"로 초기화하여 경로가 존재하지 않는지 확인합니다.
이제 3개의 중첩된 for 루프로 시작하고 0에서 V-1 사이의 범위에 k개의 정점을 적용합니다. 이 범위의 도움으로 최단 거리와 경로가 업데이트됩니다. 세 번째 중첩 루프에서는
여기서 K는 새로 업데이트된 최단 경로와 거리를 확인하는 2D 배열 행렬의 행과 열 부분을 업데이트하고 있습니다.
다음으로 다음 조건을 제공하여 모든 정점 쌍의 최단 거리와 경로를 인쇄합니다
두 개의 중첩된 for 루프를 사용하여 최단 거리와 경로를 인쇄합니다.
두 번째 for 루프 아래의 if 문을 사용하여 dist[i][j]가 무한대인지 확인합니다. 무한대인 것으로 확인되면 "INF"를 인쇄하고, 그렇지 않으면 최단 경로를 인쇄합니다.
마지막으로 세 개의 매개변수(parent[i], i, j)를 전달하여 'printPath()'라는 함수를 호출합니다.
이 프로그램에서는 Floyd Warshall 알고리즘을 사용하여 두 노드 사이의 최단 경로를 계산합니다.
#include <iostream>
using namespace std;
#define INF 1000000000 // Infinity
void printPath(int parent[], int i, int j) {
if (i == j)
cout << i << " ";
else if (parent[j] == -1)
cout << "No path exists";
else
{
printPath(parent, i, parent[j]);
cout << j << " ";
}
}
int main()
{
int V = 4;
// V represent number of vertices
int dist[V][V] = {{0, 2, INF, 4},
{6, 0, 5, 3},
{INF, 10, 0, 1},
{7, 9, 8, 0}};
// Represent the graph using adjacency matrix
// Apply the Floyd Warshall algorithm to find the shortest paths
int parent[V][V];
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] != INF && i != j)
parent[i][j] = i;
else
parent[i][j] = -1;
}
}
// update the path and distance using the k vertex range from 0 to V-1.
for (int k = 0; k < V; k++)
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
parent[i][j] = parent[k][j];
}
}
}
}
// Print shortest distances and paths between all pairs of vertices
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
cout << "The Shortest distance between " << i << " and " << j << " is ";
if (dist[i][j] == INF)
cout << "INF ";
else
cout << dist[i][j] << " ";
cout << "and the shortest path is:- ";
printPath(parent[i], i, j);
cout << endl;
}
}
return 0;
}
The Shortest distance between 0 and 0 is 0 and the shortest path is:- 0 The Shortest distance between 0 and 1 is 2 and the shortest path is:- 0 1 The Shortest distance between 0 and 2 is 7 and the shortest path is:- 0 1 2 The Shortest distance between 0 and 3 is 4 and the shortest path is:- 0 3 The Shortest distance between 1 and 0 is 6 and the shortest path is:- 1 0 The Shortest distance between 1 and 1 is 0 and the shortest path is:- 1 The Shortest distance between 1 and 2 is 5 and the shortest path is:- 1 2 The Shortest distance between 1 and 3 is 3 and the shortest path is:- 1 3 The Shortest distance between 2 and 0 is 8 and the shortest path is:- 2 3 0 The Shortest distance between 2 and 1 is 10 and the shortest path is:- 2 1 The Shortest distance between 2 and 2 is 0 and the shortest path is:- 2 The Shortest distance between 2 and 3 is 1 and the shortest path is:- 2 3 The Shortest distance between 3 and 0 is 7 and the shortest path is:- 3 0 The Shortest distance between 3 and 1 is 9 and the shortest path is:- 3 1 The Shortest distance between 3 and 2 is 8 and the shortest path is:- 3 2 The Shortest distance between 3 and 3 is 0 and the shortest path is:- 3
我们学习了使用Floyd Warshall算法找到任意两个节点之间的最短路径的概念。我们使用邻接矩阵作为程序的输入，通过它我们找到了最短路径和距离。此外，为了更新路径和距离，我们使用了k个顶点来更新行和列。在我们的日常生活中，我们在谷歌地图上搜索最短路线或路径，从一个起点到目的地。
위 내용은 Floyd-Warshal 알고리즘을 사용하여 두 노드 사이의 최단 경로를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
