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算法的实现原理，可以用来查找最短路径。

相似文章
• Dijkstra算法C++模板
  Dijkstra算法是一种用于图论问题中求解最短路径的经典算法。该算法的主要思想是从起始点开始，将所有点分为两个集合，一个集合是已经求得最短路径的点的集合，另一个集合是未求得最短路径的点的集合。每次从未求得最短路径的点中选择距离起始点最近的
  
  
• C++实现邻接表Dijkstra算法
  Dijkstra算法是一个经典的单源最短路径算法，常用于解决带权重的图问题。邻接表是一种常见的图表示方法，它由多个链表组成，每个链表代表一个节点和它所连的所有边。邻接表在使用Dijkstra算法时可以大大提高效率。本文将介绍如何使用C++实
  
  
• Dijkstra算法C++模板
  Dijkstra算法是一种用于图论问题中求解最短路径的经典算法。该算法的主要思想是从起始点开始，将所有点分为两个集合，一个集合是已经求得最短路径的点的集合，另一个集合是未求得最短路径的点的集合。每次从未求得最短路径的点中选择距离起始点最近的
  
  
• Dijkstra算法C++模板
  Dijkstra算法是最短路径算法之一，在许多应用场景中都有着重要的作用。以下是一个简单的C++实现模板。
  
  
• Java实现最短路径算法
  Java实现最短路径算法
  
  
• Java实现最短路径算法——Dijkstra算法解析与代码实现
  Java实现最短路径算法——Dijkstra算法解析与代码实现
  
  
• 《Java最短路径算法代码详解》
  《Java最短路径算法代码详解》
  
  
• Java实现最短路径算法 代码详解
  Java实现最短路径算法 代码详解
  
  
• Java实现Dijkstra算法求最短路径
  Java实现Dijkstra算法求最短路径
  
  
• Java中实现最短路径的方法
  Java中实现最短路径的方法
  
  
• Java编写最短路径算法——Dijkstra算法
  Java编写最短路径算法——Dijkstra算法
  
  
• Java实现最短路径计算
  Java实现最短路径计算
  
  
• 用Java实现最短路径算法：Dijkstra算法简介与实现
  用Java实现最短路径算法：Dijkstra算法简介与实现
  
  
• Java实现最短路径计算
  Java实现最短路径计算
  
  
• Java实现最优路径算法
  Java实现最优路径算法
  
  
• 用Java编写最短路径算法Dijkstra
  用Java编写最短路径算法Dijkstra
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政