21xrx.com
2025-03-24 18:19:52 Monday
文章检索 我的文章 写文章
使用C++实现Dijkstra算法求解最短路径
2023-06-30 15:34:34 深夜i     17     0
C++ Dijkstra算法 最短路径

Dijkstra算法是一种用于求解最短路径的经典算法，它是由荷兰计算机科学家Edsger Dijkstra在1956年开发的。该算法通过从源节点开始，在图中逐步扩展到离源节点最近的目标节点，以找到最短路径。这篇文章将介绍如何使用C++实现Dijkstra算法求解最短路径。

首先，我们需要一个表示图的数据结构。在C++中，可以使用邻接列表或邻接矩阵来表示图。在这里，我们将使用邻接列表作为示例。我们创建一个Graph类，其中包含节点、边和权重等变量和方法。

c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
// 图的边和权重
struct Edge {
  int toNode;
  int weight;
  Edge(int to, int w) : toNode(to), weight(w) {}
};
// 图的节点和到源节点的最短路径
struct Node {
  int value;
  int distance;
  vector<Edge> edges;
  bool operator<(const Node& other) const
    return distance > other.distance;
  
};
class Graph {
public:
  Graph(int n); // 构造函数
  void buildGraph(); // 添加边和权重
  void dijkstra(int s); // Dijkstra算法
private:
  vector<Node> nodes;
  int numNodes;
};

我们现在来构建构造函数和添加边和权重的方法。构造函数构建了空的图，而创建的辅助方法将连接源节点和目标节点，并为它们分配权重。

c++
Graph::Graph(int n) {
  numNodes = n;
  nodes = vector<Node> (numNodes);
}
void Graph::buildGraph() {
  // 构建图
  nodes[0].edges.push_back(Edge(1, 4));
  nodes[0].edges.push_back(Edge(2, 1));
  nodes[1].edges.push_back(Edge(2, 2));
  nodes[1].edges.push_back(Edge(3, 5));
  nodes[1].edges.push_back(Edge(4, 6));
  nodes[2].edges.push_back(Edge(1, 4));
  nodes[2].edges.push_back(Edge(3, 2));
  nodes[3].edges.push_back(Edge(4, 1));
  nodes[3].edges.push_back(Edge(5, 4));
  nodes[4].edges.push_back(Edge(5, 3));
}

现在，我们已经构建了一个空的图，下一步就是实现Dijkstra算法。Dijkstra算法需要跟踪每个节点到源节点的最短路径和它们目前的状态。在我们的实现中，我们使用了一个最小堆（或优先队列）来存储带有最短路径顺序的节点，并将跟踪节点状态的数据结构存储在我们的Node类中。为此，我们需要实现Dijkstra算法和Node类中的运算符。

c++
void Graph::dijkstra(int s) {
  priority_queue<Node> pq;
  for (int i = 0; i < numNodes; i++) {
    nodes[i].distance = INF;
  }
  nodes[s].distance = 0;
  pq.push(nodes[s]);
  while(!pq.empty()) {
    Node node = pq.top();
    for (Edge e: node.edges) {
      if (nodes[e.toNode].distance > node.distance + e.weight) {
        nodes[e.toNode].distance = node.distance + e.weight;
        pq.push(nodes[e.toNode]);
       }
    }
    pq.pop();
  }
}

运算符<比较两个节点的最短路径，并返回比较结果。我们也需要添加一个遍历跟踪最短路径的方式。

c++
bool Node::operator<(const Node& other) const
  return distance > other.distance;
void printShortestPath(int s, vector<Node> nodes) {
  cout << "最短路径：" << endl;
  for (int i = 0; i < nodes.size(); i++) {
    if (nodes[i].distance == INF)
      cout << s << " -> " << i << "：无穷大" << endl;
     else {
      cout << s << " -> " << i << "：" << nodes[i].distance << endl;
    }
  }
  cout << endl;
}

最后，我们将所有部分组合在一起，使用Graph类创建我们的图实例，并使用Dijkstra算法查找源节点到其他所有节点的最短路径。我们也将打印出路径和权重。

c++
int main() {
  Graph graph(6);
  graph.buildGraph();
  int s = 0; // 起点
  graph.dijkstra(s);
  printShortestPath(s, graph.nodes);
  return 0;
}

在运行程序后，我们可以看到以下输出：

最短路径：
0 -> 0：0
0 -> 1：3
0 -> 2：1
0 -> 3：4
0 -> 4：7
0 -> 5：10

这意味着从节点0到任何其他节点的最短路径分别为0、3、1、4、7和10。这是Dijkstra算法的实现原理，可以用来查找最短路径。

  
  

评论区