21xrx.com
2025-04-19 02:36:05 Saturday
文章检索 我的文章 写文章
Dijkstra算法C++模板
2023-06-23 14:39:10 深夜i     14     0
Dijkstra算法 C++ 模板

Dijkstra算法是最短路径算法之一，在许多应用场景中都有着重要的作用。以下是一个简单的C++实现模板。

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
const int INF = 1e9;
vector<vector<pair<int, int>>> graph;
vector<int> dist;
vector<bool> visited;
void dijkstra(int start) {
  dist[start] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  pq.push(0);
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (visited[u])
      continue;
    
    visited[u] = true;
    for (auto v : graph[u]) {
      int weight = v.second;
      int to = v.first;
      if (dist[u] + weight < dist[to]) {
        dist[to] = dist[u] + weight;
        pq.push({dist[to], to});
      }
    }
  }
}
int main() {
  int n, m, start;
  cin >> n >> m >> start;
  graph.resize(n + 1);
  dist.resize(n + 1, INF);
  visited.resize(n + 1, false);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back( w);
  }
  dijkstra(start);
  for (int i = 1; i <= n; i++) {
    if (dist[i] == INF)
      cout << "INF ";
     else {
      cout << dist[i] << " ";
    }
  }
  return 0;
}

这个模板使用了C++ STL中的vector、priority_queue、pair等容器和工具。在dijkstra函数中，我们使用了一个优先队列，每次都会将当前距离最短的节点弹出来，然后遍历与其相邻的节点（v），如果从起点（start）到结点（v）的距离+从v到u的距离小于起点到u的距离（dist[u]），则跟新dist[u]和最短距离的队列（pq），pq中的元素是pair类型，第一个元素是dist[u]，第二个是结点u的编号。

本模板的时间复杂度为O((n+m)logn)，其中n为节点数，m为边数，据说在实际应用中表现非常优秀。

  
  

评论区