C++实现Dijkstra算法 |21xrx.com

C++实现Dijkstra算法

2023-07-13 10:26:27 深夜i 15 0

C++ Dijkstra算法实现

Dijkstra算法是求解单源最短路径问题的一种经典算法，它的特点是可以对带权有向图和无向图进行求解。在实际应用中，Dijkstra算法被广泛应用于网络路由、交通流等领域。而C++是一种强大的编程语言，也是学习算法和数据结构的基本工具之一。因此，掌握用C++实现Dijkstra算法是非常有用的。

Dijkstra算法的核心思想是通过逐步扩展确定起点到各个节点最短路径的方法，直到所有节点的最短路径都被确定。实现过程中，需要用一个数组dist来记录起点到每个节点的当前最短路径长度，并使用一个数组visited来标记每个节点是否被访问过。每次从未访问过的节点中选择一个距离起点最近的节点，并更新其邻居节点的dist数组和visited数组。

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

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
vector<int> dijkstra(int s, vector<vector<pair<int, int>>> graph) {
  int n = graph.size();
  vector<int> dist(n, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  dist[s] = 0;
  pq.push(make_pair(dist[s], s));
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    for (auto v : graph[u]) {
      if (dist[v.first] > dist[u] + v.second) {
        dist[v.first] = dist[u] + v.second;
        pq.push(make_pair(dist[v.first], v.first));
      }
    }
  }
  return dist;
}
int main() {
  int n, m, s;
  cin >> n >> m >> s;
  vector<vector<pair<int, int>>> graph(n);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back(make_pair(v, w));
    graph[v].push_back(make_pair(u, w));
  }
  vector<int> dist = dijkstra(s, graph);
  for (int i = 0; i < n; i++) {
    if (dist[i] == INF)
      cout << "INF" << endl;
     else {
      cout << dist[i] << endl;
    }
  }
  return 0;
}

在上述示例代码中，我们首先定义了一个常量INF，表示正无穷，然后使用vector >>表示图，其中第一维是节点编号，第二维是一个pair，表示该节点与其相邻节点之间的边。在dijkstra函数中，我们使用一个优先队列pq来存储距离起点最近的未访问节点，并使用一个while循环逐步扩展路径，直到所有节点都被访问。最终，我们返回一个dist数组，其中dist[i]表示起点到i节点的最短路径长度。

在main函数中，我们首先从标准输入读入节点数n，边数m和起点编号s，并使用一个循环读入所有的边，然后调用dijkstra函数求解最短路径，并输出结果。

综上所述，使用C++实现Dijkstra算法并不困难，而且由于其广泛应用于实际问题中，熟练掌握该算法的实现可以帮助我们更好地理解其原理和应用场景。

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

下一篇: C++自动生成复选框（checkbox）

评论区

相似文章