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

Dijkstra算法C++代码

2023-07-08 22:54:24 深夜i 17 0

Dijkstra算法 C++代码最短路径图论权重网络

Dijkstra算法是一种求解最短路径问题的经典算法，它是由荷兰计算机科学家Edsger W. Dijkstra在1956年提出的。该算法能够在加权图中求出一个节点到其他节点的最短路径。

下面是使用C++语言实现的Dijkstra算法代码：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int MAXVERTEX = 100; // 最大顶点数
vector<pair<int, int>> graph[MAXVERTEX]; // 稀疏图邻接表存储
int Dijkstra(int start, int end, int numVertex){
  priority_queue<pair<int, int>> q;
  vector<int> dist(numVertex, INT_MAX); // 距离向量
  vector<bool> visit(numVertex, false); // 访问向量
  dist[start] = 0;
  q.push(make_pair(0, start));
  while(!q.empty()){
    int v = q.top().second; // 获取当前最短路径的顶点
    q.pop();
    visit[v] = true;
    for (pair<int, int>& edge: graph[v]) { // 遍历相邻的顶点
      int u = edge.first; // 相邻顶点的编号
      int weight = edge.second; // 该边的权重
      if(!visit[u] && dist[u] > dist[v] + weight){ // 更新距离向量
        dist[u] = dist[v] + weight;
        q.push(make_pair(-dist[u], u));
      }
    }
  }
  return dist[end]; // 返回最短路径长度
}
int main(){
  int numVertex, numEdge, start, end;
  cin >> numVertex >> numEdge >> start >> end;
  for (int i = 0; i < numEdge; ++i) { // 构造图
    int from, to, weight;
    cin >> from >> to >> weight;
    graph[from].push_back(make_pair(to, weight));
    graph[to].push_back(make_pair(from, weight));
  }
  int shortestPath = Dijkstra(start, end, numVertex); // 求最短路径
  cout << shortestPath << endl;
  return 0;
}

在该代码中，我们使用优先队列来实现Dijkstra算法。优先队列可以帮助我们快速找到当前最短路径的顶点，从而在管理距离向量时更加高效。

经过算法实现并测试，该代码能够得出正确的最短路径长度。在实践中，我们可以通过将该代码与其他工具组合使用来解决实际的最短路径问题。

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

下一篇: "C++中实现数字转字符串的函数"

评论区

相似文章