单源最短路问题(SSSP)常用的算法有Dijkstra，Bellman-Ford，这两个算法进行优化，就有了Dijkstra+heap、SPFA(Shortest Path Faster Algorithm)算法。这两个算法写起来非常相似。下面就从他们的算法思路、写法和适用场景上进行对比分析。
Dijkstra
- 找到未标记的dis最小的点,标记，松弛它连接的点的边
- Dijkstra是每次确定了到一个点的最短距离，再用该点更新到其它点的距离。不能处理有负边的图。
while(true)
{
int v=-1;
for(int j=1;j<=n;j++)
{
if(vis[j]!=1&&(v==-1||dis[v]>dis[j]))//找到最小的距离的点
{
v=j;
}
}
if(v==-1)
{
break;
}
vis[v]=1;//标记
for(int j=1;j<=n;j++)
{
if(!vis[j])
{
dis[j]=min(dis[j],dis[v]+mp[v][j]);//松弛它连接的边，不连接的距离是INF
}
}
}
Dijkstra+优先队列优化
- 出队列的点是dis是最小的点
void Dijkstra(int x,int n)
{
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));
dis[x]=0;//初始起点距离为0；
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qu;//优先队列
qu.push(make_pair(0,x));//距离，节点
while(!qu.empty( ))
{
int u=qu.top( ).second;//距离dis最小的节点
qu.pop( );
if(!vis[u])//没有标记
{
vis[u]=1;//标记
for(int i=1;i<=n;i++)
{
if(dis[i]>dis[u]+mp[u][i])//更新它连接的点的距离
{
dis[i]=dis[u]+mp[u][i];
qu.push(make_pair(dis[i],i));
}
}
}
}
}
Checking an Alibi
- 最短路
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int head[2100],cnt;
struct node
{
int v,w;
int nxt;
}edge[2100];
int vis[1110];
int dis[1110];
int n,m,c,t;
void add(int x,int y,int w)
{
edge[++cnt].nxt=head[x];
edge[cnt].v=y;
edge[cnt].w=w;
head[x]=cnt;
}
void Dijkstra(int dis[ ])
{
memset(vis,0,sizeof(vis));
dis[1]=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qu;//优先队列
qu.push(make_pair(0,1));
while(!qu.empty( ))
{
int u=qu.top( ).second;
qu.pop( );
if(!vis[u])
{
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].nxt)
{
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
qu.push(make_pair(dis[v],v));
}
}
}
}
}
int main( )
{
int x,y,w;
scanf("%d%d%d%d",&n,&m,&c,&t);
cnt=0;
memset(head,-1,sizeof(head));
memset(dis,INF,sizeof(dis));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
Dijkstra(dis);
// for(int i=1;i<=n;i++)
// {
// cout<<dis[i]<<" ";
// }
// cout<<endl;
int ans=0;
priority_queue<int,vector<int>,greater<int> >q;
for(int i=1;i<=c;i++)
{
scanf("%d",&x);
if(dis[x]<=t)
{
q.push(i);
ans++;
}
}
printf("%d\n",ans);
while(!q.empty( ))
{
printf("%d\n",q.top( ));
q.pop( );
}
return 0;
}
Spfa(可判断负环）
- 对所有边松弛
- SPFA是用双端队列，每次取出队头，来更新距离，它之后可能还会入队。它是一种动态逼近法，因为每次松弛距离都会减小，所以松弛一定会有结束的。如果一个点入队超过n次就是存在负环。
spfa+队列优化
while(!q.empty())
{
int u=q.front(); q.pop();//出队
vis[u]=false;//标记取消
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(d[u]+e[i].w<d[v])
{
d[v]=d[u]+e[i].w;
if(!vis[v])//不在队列中
{
vis[v]=true;//标记
q.push(v);//加入队列
}
}
}
}
spfa判断负环
int spaf(int x,int n)
{
memset(vis,0,sizeof(vis));
memset(mark,0,sizeof(mark));
memset(dis,INF,sizeof(dis));
queue<int>qu;//普通队列
qu.push(x);
dis[x]=0;
vis[x]=1;
mark[x]=1;
while(!qu.empty( ))
{
int u=qu.front( );
qu.pop( );
vis[u]=0;
for(int i=1;i<=n;i++)
{
if(dis[i]>dis[u]+mp[u][i])
{
dis[i]=dis[u]+mp[u][i];
if(!vis[i])
{
qu.push(i);
mark[i]++;
if(mark[i]>=n)//当一个点进入队列的次数大于等于n次，说明有负环
{
return 1;
}
vis[i]=1;
}
}
}
if(dis[x]<0)
{
return 1;
}
}
return 0;
}
Wormholes
- 有负环输出YES,否则NO
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int mp[550][550];
int dis[550];
int vis[550];
int mark[550];
int n,k,m;
int spaf(int x,int n)
{
memset(vis,0,sizeof(vis));
memset(mark,0,sizeof(mark));
memset(dis,INF,sizeof(dis));
queue<int>qu;//普通队列
qu.push(x);
dis[x]=0;
vis[x]=1;
mark[x]=1;
while(!qu.empty( ))
{
int u=qu.front( );
qu.pop( );
vis[u]=0;
for(int i=1;i<=n;i++)
{
if(dis[i]>dis[u]+mp[u][i])
{
dis[i]=dis[u]+mp[u][i];
if(!vis[i])
{
qu.push(i);
mark[i]++;
if(mark[i]>=n)//当一个点进入队列的次数大于等于n次，说明有负环
{
return 1;
}
vis[i]=1;
}
}
}
if(dis[x]<0)
{
return 1;
}
}
return 0;
}
int main ( )
{
int t,x,y,w;
scanf("%d",&t);
while(t--)
{
memset(mp,INF,sizeof(mp));
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
mp[i][i]=0;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
mp[x][y]=mp[y][x]=min(mp[x][y],w);
}
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&x,&y,&w);
mp[x][y]=min(mp[x][y],-w);
}
if(spaf(1,n))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
「参考链接」
网友评论