C++实现最短路径算法 |21xrx.com

C++实现最短路径算法

2023-07-01 01:25:42 深夜i -- --

C++ 最短路径算法实现

C++是一种功能强大的编程语言，可以用于开发各种类型的应用程序。在计算机科学领域，C++也被广泛应用于开发算法和数据结构等方面。其中，最短路径算法是一种常见的算法，主要用于计算两个节点之间的最短距离。本文将介绍如何使用C++实现最短路径算法。

首先，需要了解最短路径算法的基本思想。最短路径算法根据给定的权值来计算两点之间的最短距离。在图形中，每一个节点表示一个点，每一个边表示两个节点之间的距离。最短路径算法根据这些边的权值计算最短路径。

有多种实现最短路径算法的方法，其中最常见的包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。下面将以Dijkstra算法为例介绍如何使用C++实现最短路径算法。

Dijkstra算法是一种贪心算法，主要用于计算带权有向图中的单源最短路径。具体的实现步骤如下：

1. 初始化距离数组：为了计算距离，需要初始化源节点到所有其他节点的距离。在第一次迭代中，源节点到自身的距离为0，所有其他节点的距离为无穷大。

2. 查找最小距离的节点：从未标记的节点中选择距离最近的节点。

3. 更新距离数组：根据选择的节点更新距离数组。如果通过节点x可以到达节点y，并且从源节点到x的距离加上从x到y的距离比从源节点到y的距离小，就更新距离数组。

4. 标记选择的节点：对选择的节点进行标记，表示已经计算出从源节点到该节点的最短距离。

5. 重复以上步骤，直到所有节点都被标记。

下面是使用C++实现Dijkstra算法的代码示例：


#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 1e9;
vector<pair<int, int>> g[1000];
int dist[1000];
void dijkstra(int start) {
 memset(dist, INF, sizeof(dist));
 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 pq.push( start);
 dist[start] = 0;
 while (!pq.empty()) {
  int u = pq.top().second;
  pq.pop();
  if (dist[u] == INF) continue;
  for (auto v : g[u]) {
   if (dist[u] + v.second < dist[v.first]) {
    dist[v.first] = dist[u] + v.second;
    pq.push({dist[v.first], v.first});
   }
  }
 }
}
int main() {
 int n, m;
 cin >> n >> m;
 for (int i = 0; i < m; i++) {
  int u, v, w;
  cin >> u >> v >> w;
  g[u].push_back(v);
 }
 dijkstra(1);
 for (int i = 1; i <= n; i++) {
  cout << dist[i] << " ";
 }
 cout << endl;
 return 0;
}

在此示例中，我们使用了一个邻接列表来存储图形。其中，变量g是一个向量数组，其每个元素是一个向量，也就是每个节点的相邻节点及其边的权值。变量dist用来存储源节点到其他所有节点的距离。我们先将距离数组初始化为无穷大，表示源节点到所有节点的距离都未知。接着，我们使用一个优先级队列pq来选择距离最小的节点。每次迭代中，我们从pq中选择距离最近的节点，将其标记为已访问，并更新与该节点相邻的所有节点的距离。

最后，我们输出距离数组中所有节点的最短距离。此时，dist[i]存储了源节点到i节点的最短距离。

综上，我们可以看到，使用C++实现最短路径算法是非常简单的。只需要使用合适的数据结构，加上一些简单的迭代和条件判断，就可以轻松实现最短路径算法。

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

下一篇: C++实现开根号的代码

评论区

()

相似文章