21xrx.com
2024-11-05 16:33:43 Tuesday
登录
文章检索 我的文章 写文章
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算法是一种经典的图论算法,在各种应用场景中得到了广泛的应用。掌握其思想和实现方式,对于提高算法和程序设计的能力具有重要意义。

  
  

评论区

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