21xrx.com
2024-12-23 00:23:47 Monday
登录
文章检索 我的文章 写文章
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算法。通过定义图的数据结构并使用优先队列实现算法,我们可以轻松地计算源节点到其他所有节点的最短路径。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复