一、弗洛伊德(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)
No responses yet