使用弗洛伊德-沃沙尔算法找到任意两个节点之间的最短路径-C++-PHP中文网

使用弗洛伊德-沃沙尔算法找到任意两个节点之间的最短路径

王林

发布： 2023-09-20 14:21:12

转载

857人浏览过

c++有一个宏，它被定义为一段代码或期望的值，并且每当用户需要时，它将被重复使用。弗洛伊德-沃尔夏尔算法是在给定的加权图中找到所有顶点对之间最短路径的过程。该算法遵循动态规划的方法来找到最小权重图。

让我们通过图表来理解弗洛伊德-沃尔夏尔算法的含义 -

以顶点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[][] array_name;

登录后复制

参数

data_type[][] - 用户提到的数据类型。第一个数组代表行，第二个数组代表列。所以，这代表了二维数组。

array_name - 为数组指定的名称。

算法

我们将使用头文件 'iostream' 启动程序，并将宏位置定义为 'INF'（无穷大），因为稍后它将满足二维数组矩阵和 if-else 语句。
接下来，我们创建名为 'printPath' 的全局函数定义，并接受三个参数，即 'parent[]'、'i' 和'j' 验证路径是否存在。
然后我们开始主函数，并将值‘4’存储到变量‘V’中，该变量表示顶点的数量。其次，将值以邻接矩阵的形式存储到变量‘dist[V][V]’中。正如我们所知，dist[i][j]表示2D矩阵，它定义了从‘i’到‘j’的边的权重，通过存储邻接矩阵。

德语写作助手
德语助手旗下的AI智能写作平台，支持对德语文本进行语法词汇纠错、润色、扩写等AI功能。

0

查看详情
接下来，我们正在为变量‘parent’初始化2D数组，并且大小为[V][V]。

在此变量中，我们用来显示每对顶点 'i' 和 'j' w.r.t 'parent[i][j]'.

通过使用两个嵌套的for循环，我们将找到最短路径。第一个for循环迭代矩阵中的行。然后，通过第二个for循环迭代矩阵中的列，然后我们将使用if-else语句检查以下条件 -

如果 (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]”，以验证该路径不存在。

现在我们从三个嵌套的 for 循环开始，并在 0 到 V-1 的范围内应用 k 个顶点，在这个范围的帮助下，我们的最短距离和路径将被更新。在第三个嵌套循环中，我们使用以下条件，例如

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];	
}

登录后复制

这里 K 正在更新二维数组矩阵中的行和列的部分，这验证了新更新的最短路径和距离。

接下来，我们通过给定以下条件，打印出所有顶点对的最短距离和路径

通过使用两个嵌套的 for 循环，我们打印最短距离和路径。
通过在第二个for循环下使用if语句，我们将检查dist[i][j]是否等于无穷大。如果发现它是无穷大，则打印“INF”，否则打印最短路径。

最后，我们调用名为 'printPath()' 的函数，通过传递三个参数（parent[i]、i、和j。

示例

在这个程序中，我们将使用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

登录后复制