Dijkstra算法C++模板 |21xrx.com

Dijkstra算法C++模板

2023-07-09 02:05:27 深夜i -- --

Dijkstra 算法 C++ 模板

Dijkstra算法是解决单源最短路径问题的一种经典算法。在计算机科学领域中应用广泛。

C++是一种高效、灵活的编程语言，它在算法实现中具有很强的优势。下面是Dijkstra算法的C++模板，供大家参考。

1. 实现思路

Dijkstra算法通过维护一个距离最小的顶点集合S，以及到达该集合中顶点的最短距离的数组d，来逐步扩展S并更新d数组。

具体实现中，我们使用一个优先队列（即堆）来维护扩展S的过程，将d值最小的顶点加入S中，并以该顶点为起点，更新所有未被访问的顶点的d值。每个顶点只被访问一次，因此算法时间复杂度为 O(E+VlogV)，其中E为边数，V为顶点数。

2. C++代码实现

以下是一个基于STL库实现的Dijkstra算法模板，其输入为邻接表表示的图和源点编号s，输出为源点到各个顶点的最短距离。其中，顶点编号从0开始。


#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 10010;
const int INF = 0x3f3f3f3f;
struct Edge
{
  int to, dis;
  Edge(int t = 0, int d = 0) : to(t), dis(d) { }
};
vector<Edge> G[MAXN];
int d[MAXN];
bool vis[MAXN];
void Dijkstra(int s)
{
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
  memset(d, INF, sizeof(d));
  memset(vis, 0, sizeof(vis));
  d[s] = 0;
  q.push(make_pair(0, s));
  while (!q.empty())
  {
    int u = q.top().second;
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = 0; i < G[u].size(); i++)
    {
      Edge& e = G[u][i];
      if (d[e.to] > d[u] + e.dis)
      {
        d[e.to] = d[u] + e.dis;
        q.push(make_pair(d[e.to], e.to));
      }
    }
  }
}
int main()
{
  int n, m, s;
  scanf("%d%d%d", &n, &m, &s);
  for (int i = 0; i < m; i++)
  {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    G[u].push_back(Edge(v, w));
  }
  Dijkstra(s);
  for (int i = 0; i < n; i++)
    printf("%d ", d[i]);
  printf("\n");
  return 0;
}

3. 总结

Dijkstra算法是一种经典的单源最短路径算法，在实际应用中具有广泛的用途。通过使用C++语言提供的STL库，我们可以实现高效、简洁、可读性高的代码。对于需要进行算法实现的读者，建议掌握算法原理的同时，结合自己的编程实践，不断提升自己的编程能力。

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

下一篇: C++数据查找程序

评论区

()

相似文章