C++实现Dijkstra算法 |21xrx.com

C++实现Dijkstra算法

2023-07-02 12:48:26 深夜i 12 0

C++ Dijkstra算法实现

Dijkstra算法是一种用于解决带有权值的图的单源最短路径问题的经典算法。它的核心思想是从源节点开始，通过贪心的方式一步步地找到距离源节点最近的节点，并将其纳入最短路径集合。经过迭代，直到所有节点都被纳入最短路径集合。

C++是一种高性能、高效的编程语言，在实现Dijkstra算法时，C++可以提供高效的数据结构和算法库，能够很好地支持Dijkstra算法。下面是一个使用C++实现Dijkstra算法的示例：

#include<iostream>
#include<limits.h>
#include<vector>
#include<queue>
using namespace std;
#define N 200005
#define INF INT_MAX
struct node
wedge[2*N];
int head[N];
long long d[N];
int vis[N],cnt[N];
int n,m,s,t,k;
void add_edge(int u,int v,int w)
{
 edge[++k].u=u;
 edge[k].v=v;
 edge[k].w=w;
 edge[k].next=head[u];
 head[u]=k;
}
void dijkstra(int s)
{
 for(int i=1;i<=n;i++)
 d[i]=INF;
 priority_queue< pair<long long,int> > q;
 q.push(make_pair((long long)0,s));
 d[s]=0;
 vis[s]=1;
 while(!q.empty())
 {
  long long dis=-q.top().first;
  int u=q.top().second;
  q.pop();
  vis[u]=0;
  for(int i=head[u];i;i=edge[i].next)
  {
   int v=edge[i].v;
   if(d[v]>dis+edge[i].w)
   {
    d[v]=dis+edge[i].w;
    if(!vis[v])
    {
      if(++cnt[v]>n)
      
       cout<<-1<<endl;
       return;
      
     vis[v]=1;
     q.push(make_pair((long long)(-d[v]),v));
    }
   }
  }
 }
 if(d[t]==INF)
 cout<<-1<<endl;
 else
 cout<<d[t]<<endl;
}
int main()
{
 cin>>n>>m>>s>>t;
 for(int i=1;i<=m;i++)
 {
  int u,v,w;
  cin>>u>>v>>w;
  add_edge(u,v,w);
 }
 dijkstra(s);
 return 0;
}

在这个示例代码中，我们使用了C++中的STL库中的priority_queue来实现堆优化的Dijkstra算法。priority_queue是一个用于存储元素并按优先级排序的容器，算法中将队列中的节点按照距离递增的方式排序，每次取出队首元素进行松弛操作，这种方式可以使得每次松弛的时间复杂度降为O(logN)。

总结来说，使用C++实现Dijkstra算法非常方便快捷，可以用STL库中的优先队列来实现堆优化的Dijkstra算法，同时，C++还可以提供更高效的数据结构和算法库，进一步优化实现的效率。

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

下一篇: Node.js IO密集型。

评论区

相似文章