21xrx.com
2025-04-04 21:49:36 Friday
文章检索 我的文章 写文章
C++实现Dijkstra算法
2023-07-01 19:35:19 深夜i     16     0
C++ Dijkstra算法 最短路径 图 优先队列

Dijkstra算法是一种用于计算单源最短路径的算法。该算法是由荷兰计算机科学家Edsger W. Dijkstra在1956年开发的，并在计算机科学中广泛使用。这种算法可以用于解决很多问题，如城市交通、电子网络等等。

C++是一种流行的编程语言，它是一种高效的、静态类型的、面向对象的编程语言。C++已经成为工业界中最值得信赖的编程语言之一。现在，让我们看看如何使用C++实现Dijkstra算法。

首先，我们需要定义一个Graph类来代表我们的图。该类将包括节点、边和权重。我们需要定义一个函数来添加节点和边，以及计算最短路径。在这个函数中，我们将使用最小堆来维护未考虑的节点集合，这个过程我们称之为“松弛算法”，该算法的实现是通过比较当前节点到终点的距离和已知距离之和来更新节点的距离。

下面是C++实现Dijstra算法的示例代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100
#define INF INT_MAX
class Node {
public:
  int weight, dest;
  Node(int weight, int dest) : weight(weight), dest(dest) {}
};
class Graph {
public:
  vector<Node> adjList[MAX];
  int distances[MAX];
  void addEdge(int src, int dest, int weight) {
    adjList[src].push_back(Node(weight, dest));
  }
  void dijkstra(int src, int n) {
    for (int i = 0; i < n; i++) {
      distances[i] = INF;
    }
    distances[src] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, src));
    while (!pq.empty()) {
      int u = pq.top().second;
      pq.pop();
      for (auto &v: adjList[u]) {
        if (distances[v.dest] > distances[u] + v.weight) {
          distances[v.dest] = distances[u] + v.weight;
          pq.push(make_pair(distances[v.dest], v.dest));
        }
      }
    }
  }
};
int main() {
  Graph graph;
  int n, m, src, dest, weight;
  cout << "Enter the number of nodes and edges for the graph: ";
  cin >> n >> m;
  cout << "Enter the source node: ";
  cin >> src;
  for (int i = 0; i < m; i++) {
    cout << "Edge " << i + 1 << ":\n";
    cout << "Source node: ";
    cin >> src;
    cout << "Destination node: ";
    cin >> dest;
    cout << "Weight: ";
    cin >> weight;
    graph.addEdge(src, dest, weight);
  }
  graph.dijkstra(0, n);
  for (int i = 0; i < n; i++) {
    cout << "The minimum distance from node " << src << " to node " << i << " is " << graph.distances[i] << "\n";
  }
  return 0;
}

在上面的代码中，我们首先定义了一个节点类“Node”并用它来表示图中的边。然后我们定义了一个“Graph”类，并在类中添加了节点和边的函数。我们还定义了一个“dijkstra”函数来计算从源节点到目标节点的最短路径。这个算法使用了优先级队列和松弛算法。最后，在主函数中，我们为图设置了源节点、目标节点和边，然后通过调用dijkstra函数计算了从源节点到目标节点的最短路径。

最后，通过上述的实现，我们可以用C++方便、快捷地实现Dijkstra算法，并通过优先级队列进行快速处理。如果你正在学习C++和图论，这是一个不错的实践案例。

  
  

评论区

请求出错了