21xrx.com
2024-11-10 00:28:29 Sunday
登录
文章检索 我的文章 写文章
Dijkstra算法C++模板
2023-06-23 14:39:10 深夜i     --     --
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为边数,据说在实际应用中表现非常优秀。

  
  

评论区

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