Floyd-Warshal 알고리즘을 사용하여 두 노드 사이의 최단 경로를 찾습니다.

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