一、弗洛伊德(Floyd)

for(int k=1;k<=n;k++)
   for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           sav[i][j]=min(sav[i][j],sav[i][k]+sav[k][j]);
//邻接矩阵
//O(n^3)

二、贝尔曼-福德(Bellman-Ford)

for(int j=1;j<=n-1;j++)
   for(int i=1;i<=m;i++)
      dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);
//存储有向边
//O((n-1)*m)

三、Dijkstra

priority_queue<pair<int,int> >q;
void dijkstra(int s){
   memset(dis,0x7f,sizeof(dis));
   memset(vis,0,sizeof(vis));
   q.push(make_pair(0,s);
   dis[s]=0;
   while(!q.empty()){
        int x=q.top.second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i]){
            int y=v[i],z=w[i];
            if(dis[y]>dis[x]+z){
               dis[y]=dis[x]+z;
               q.push(make_pair(-dis[y],y);
            }
        }
   }
}
//邻接表村边
//O((n+m)logm)

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类