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

C++实现Dijkstra算法

2023-07-05 17:24:37 深夜i -- --

C++ Dijkstra算法权重最短路径图算法实现

Dijkstra算法是一种经典的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。本文将介绍如何使用C++语言实现Dijkstra算法。

首先，我们需要定义一个图的数据结构，该数据结构应该包含一个表示节点的向量和另一个表示边的向量。每个边都应该包含源节点，目标节点和边的权重。

接下来，我们需要定义一个辅助函数用于查找源节点到给定节点的最短距离。该函数应该遍历图中的所有节点，并使用Dijkstra算法计算每个节点与源节点之间的最短路径。我们可以使用一个优先队列来实现这个过程，该队列按照距离排序，每次从队列中选择具有最小距离的节点。这个过程会不断更新最短路径，直到所有节点都被遍历过。

最后，我们可以使用主函数调用上述函数，并输出最短路径。具体实现代码如下：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
struct edge weight;
;
vector<int> dijkstra(vector<vector<edge>> graph, int source) {
  vector<int> distances(graph.size(), INF);
  distances[source] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  pq.push(make_pair(0, source));
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    for (const auto &e : graph[u]) {
      int v = e.to;
      int weight = e.weight;
      if (distances[v] > distances[u] + weight) {
        distances[v] = distances[u] + weight;
        pq.push(make_pair(distances[v], v));
      }
    }
  }
  return distances;
}
int main() {
  int n, m, source;
  cin >> n >> m >> source;
  vector<vector<edge>> graph(n);
  for (int i = 0; i < m; i++) {
    int u, v, weight;
    cin >> u >> v >> weight;
    graph[u].push_back(v);
  }
  auto distances = dijkstra(graph, source);
  for (const auto &distance : distances)
    cout << distance << " ";
  
  return 0;
}

本文介绍了如何使用C++实现Dijkstra算法。通过定义图的数据结构并使用优先队列实现算法，我们可以轻松地计算源节点到其他所有节点的最短路径。

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

下一篇: C++代码点击（教程）

评论区

相似文章