C++实现邻接矩阵最短路径查找 |21xrx.com

C++实现邻接矩阵最短路径查找

2023-07-11 05:00:10 深夜i -- --

C++ 邻接矩阵最短路径查找

邻接矩阵是图形结构中表示图形的一种方式，可以用来表示图形中各个节点之间的联系。在许多应用中，查找最短路径是非常重要的问题，例如，网络路由、航空公司调度等。C++是一种高效的编程语言，在实现邻接矩阵最短路径查找方面也非常适合。下面我们将讨论如何使用C++实现邻接矩阵最短路径查找。

邻接矩阵是一个二维数组，其中每个元素表示两个节点之间的距离或者权重。如果两个节点之间没有任何联系，则用无穷大或者其他代表无穷大的值表示。我们可以用以下方式来表示一个邻接矩阵：


int graph[V][V] = {
  7,
 8,
  INF,
  INF
};

其中V表示节点的数量，INF表示两个节点之间没有联系。在上述示例中，我们定义了一个4个节点的图形。

实现最短路径查找的算法有很多种，例如迪杰斯特拉算法和贝尔曼-福德算法等。在本例中，我们将使用弗洛伊德算法来查找最短路径。弗洛伊德算法通过计算所有节点对之间的最短路径来查找最短路径。算法的核心思想是动态规划，通过递推计算得到最短路径。

以下是用C++实现的弗洛伊德算法的代码：


void floydWarshall(int graph[][V]) {
 int dist[V][V], i, j, k;
 
 // 将输入矩阵复制到输出矩阵中
 for (i = 0; i < V; i++) {
  for (j = 0; j < V; j++) {
   dist[i][j] = graph[i][j];
  }
 }
 
 // 对所有中间节点进行计算
 for (k = 0; k < V; k++) {
  for (i = 0; i < V; i++) {
   for (j = 0; j < V; j++) {
    // 如果节点i经过节点k到达节点j的距离小于直接到达节点j的距离，则更新
    if (dist[i][k] + dist[k][j] < dist[i][j]) {
     dist[i][j] = dist[i][k] + dist[k][j];     
    }
   }
  }
 }
 
 // 打印最短路径矩阵
 printSolution(dist);
}

我们首先将输入矩阵复制到输出矩阵中。接着，对于所有中间节点，我们逐个计算从一个节点到另一个节点的最短路径。如果路径经过中间节点，则计算从起点到中间节点的距离，再计算从中间节点到终点的距离，最后比较直接到达终点的距离，如果通过中间节点的距离小于直接到达终点的距离，则更新最短路径。最后，我们打印出最短路径矩阵。

现在我们编写一个用于打印最短路径矩阵的函数printSolution。


void printSolution(int dist[][V]) {
 cout<<"The shortest path between every pair of vertices:"<<endl;
 for (int i = 0; i < V; i++) {
  for (int j = 0; j < V; j++) {
   if (dist[i][j] == INF)
    cout<<"INF"<<"  ";
    else {
    cout<<dist[i][j]<<"  ";
   }
  }
  cout<<endl;
 }
}

现在我们已经完成了C++实现的邻接矩阵最短路径查找。下面是完整的代码：


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define V 4
#define INF 99999
void printSolution(int dist[][V]);
void floydWarshall(int graph[][V]) {
 int dist[V][V], i, j, k;
 
 // 将输入矩阵复制到输出矩阵中
 for (i = 0; i < V; i++) {
  for (j = 0; j < V; j++) {
   dist[i][j] = graph[i][j];
  }
 }
 
 // 对所有中间节点进行计算
 for (k = 0; k < V; k++) {
  for (i = 0; i < V; i++) {
   for (j = 0; j < V; j++) {
    // 如果节点i经过节点k到达节点j的距离小于直接到达节点j的距离，则更新
    if (dist[i][k] + dist[k][j] < dist[i][j]) {
     dist[i][j] = dist[i][k] + dist[k][j];     
    }
   }
  }
 }
 
 // 打印最短路径矩阵
 printSolution(dist);
}
void printSolution(int dist[][V]) {
 cout<<"The shortest path between every pair of vertices:"<<endl;
 for (int i = 0; i < V; i++) {
  for (int j = 0; j < V; j++) {
   if (dist[i][j] == INF)
    cout<<"INF"<<"  ";
    else {
    cout<<dist[i][j]<<"  ";
   }
  }
  cout<<endl;
 }
}
int main() {
 int graph[V][V] = {
  0,
   2,
  5,
   0
 };
 floydWarshall(graph);
 return 0;
}

以上就是我们利用C++来实现邻接矩阵最短路径查找的完整代码。将输入矩阵复制到输出矩阵中，然后按照动态规划方式计算每个节点之间的最短路径。这种方法可以在较短的时间内获得所有节点之间的最短路径，特别适用于小型图形。在处理大型图形时，速度可能较慢，因此需要考虑其他方法来查找最短路径。

上一篇: idea打包java可执行jar包

下一篇: C++内存管理PDF资料

评论区

()

相似文章