Dijkstra算法C++代码 |21xrx.com

Dijkstra算法C++代码

2023-07-05 19:53:35 深夜i -- --

Dijkstra算法 C++ 代码

Dijkstra算法是一种经典的图论算法，用于在有向无环图中寻找最短路径。Dijkstra算法的基本思想是从起点开始，依次遍历每个节点，更新起点到每个节点的最短路径，并记录下这个节点的前一个节点。在完成对每个节点的遍历后，得到了从起点到每个节点的最短路径。

以下是Dijkstra算法的C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//定义节点类型
struct Node {
  int id; //节点编号
  int cost; //到该节点的最小代价
  bool operator<(const Node& other) const
    return cost > other.cost;
   //因为要使用优先队列，所以定义"<"运算符
};
const int INF = 1000000000;
//graph表示邻接矩阵，节点从0到n-1编号
int dijkstra(vector<vector<int>>& graph, int n, int start, int end) {
  vector<int> dist(n, INF); //记录起点到各个节点的最小代价
  vector<int> prev(n, -1); //记录当前节点的前一个节点
  bool visited[n] = {false}; //记录节点是否已经访问过
  dist[start] = 0; //起点到起点的代价为0
  priority_queue<Node> q; //定义优先队列，实现Dijkstra算法的关键
  q.push({start, dist[start]}); //将起点加入队列中
  while (!q.empty()) {
    Node curr = q.top();
    q.pop();
    if (visited[curr.id]) continue; //如果当前节点已经被访问过，则不再处理
    visited[curr.id] = true; //将当前节点标记为已访问
    if (curr.id == end) break; //如果当前节点为终点，则直接结束算法
    for (int i = 0; i < n; i++) {
      if (graph[curr.id][i] == INF) continue; //如果当前节点到该节点没有边，则跳过
      int newDist = dist[curr.id] + graph[curr.id][i];
      if (newDist < dist[i]) { //如果通过当前节点可以更新该节点的最小代价
        dist[i] = newDist;
        prev[i] = curr.id; //记录当前节点为该节点的前一个节点
        q.push({i, dist[i]}); //加入队列中
      }
    }
  }
  //如果终点是不可达的，返回-1
  if (dist[end] == INF) return -1;
  //打印路径
  vector<int> path;
  int curr = end;
  while (curr != start) {
    path.push_back(curr);
    curr = prev[curr];
  }
  path.push_back(start);
  for (int i = path.size() - 1; i >= 0; i--) {
    if (i != path.size() - 1) cout << " -> ";
    cout << path[i];
  }
  cout << endl;
  //返回起点到终点的最小代价
  return dist[end];
}
int main() {
  int n = 5; //图中节点数
  //邻接矩阵表示有向图
  vector<vector<int>> graph = {
     INF,
     0,
     4,
     0,
     6
  };
  int start = 0, end = 4; //设置起点和终点
  int cost = dijkstra(graph, n, start, end);
  cout << "最小代价为：" << cost << endl; //输出最小代价
  return 0;
}

上述代码以有向图的邻接矩阵表示为输入，实现了Dijkstra算法的核心思想。首先定义了节点类型，包括节点编号和起点到该节点的最小代价。这里通过重载运算符"<"实现了定义节点的优先级，以实现Dijkstra算法中的优先队列。然后，用邻接矩阵表示图，并定义了几个变量：起点到各个节点的最小代价（dist）、当前节点的前一个节点（prev）和节点是否已经访问过（visited）。最后，在循环中不断地更新起点到各个节点的最小代价，并记录下前一个节点，最终输出从起点到终点的最小代价，并输出路径。

Dijkstra算法是一种经典的图论算法，在各种应用场景中得到了广泛的应用。掌握其思想和实现方式，对于提高算法和程序设计的能力具有重要意义。

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

下一篇: 【教程】C++中如何表示无穷大

评论区

相似文章