21xrx.com
2024-12-22 22:27:07 Sunday
登录
文章检索 我的文章 写文章
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']}}
()
回复
回复