C++贪心算法求解单源点最短路径问题 |21xrx.com

C++贪心算法求解单源点最短路径问题

2023-06-22 09:06:41 深夜i 7 0

C++ 贪心算法单源点最短路径问题

单源点最短路径问题是计算图中指定起点到所有其他节点的最短路径问题。在计算机科学中，解决这个问题的算法有很多，其中贪心算法是一种计算效率比较高的算法之一。

C++语言是一种通用的高级编程语言，它支持多种编程风格，比如面向对象、过程式和函数式编程。C++中提供了STL库，其中包含了许多算法，如sort, reverse, find, count等，这些算法都可以较为高效地实现各种计算任务。贪心算法是一种典型的解决问题的算法，我们可以使用它来解决单源点最短路径问题。

在C++中，我们可以使用Dijkstra算法来解决单源点最短路径问题。具体思路如下：

1. 初始化所有节点的距离为无穷大，并将当前节点到起点的距离设置为0。

2. 将起点加入到一个优先队列中。

3. 每次从优先队列中选取距离起点最近的节点。

4. 对于该节点的每一个邻居，更新其距离，计算方法是原先的距离加上该邻居节点与该节点的距离。

5. 将每个被更新的邻居节点加入优先队列。

6. 重复第3-5步，直到优先队列为空。

代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x7fffffff;
int main()
{
  int n, m, start;
  cin >> n >> m >> start;
  vector<vector<pair<int, int>>> graph(n + 1);
  vector<int> dist(n + 1, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back( w);
  }
  dist[start] = 0;
  pq.push(0);
  while (!pq.empty()) {
    auto [curDist, curNode] = pq.top();
    pq.pop();
    if (curDist > dist[curNode])
      continue;
    for (auto [nei, w] : graph[curNode]) {
      if (curDist + w < dist[nei]) {
        dist[nei] = curDist + w;
        pq.push({dist[nei], nei});
      }
    } 
  }
  for (int i = 1; i <= n; i++) {
    if (dist[i] == INF)
      cout << "INF" << endl;
    else
      cout << dist[i] << endl;
  }
  return 0;
}

上述代码中，我们使用了优先队列来实现Dijkstra算法。该算法的时间复杂度为O(E log V)，其中E是边数，V是节点数。因此，贪心算法是解决单源点最短路径问题的一种较为高效的算法。

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

下一篇: C++类的成员变量

评论区

相似文章