Floyd
十分暴力方便的最短路算法
虽然复杂度较高，但好在有最短路的图都可以用它解决（即无负环）
int n,m;//n个节点 m条边
int mp[N][N];
void init_floyd()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
mp[i][j]=Inf;
}
mp[i][i]=0;
}
}
void floyd()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
//以 k 为中间节点尝试优化 i 到 j 的路径
if(mp[i][j]>mp[i][k]+mp[k][j])
mp[i][j]=mp[i][k]+mp[k][j];
//使用邻接矩阵原因如上
}
}
}
}
int main()
{
cin>>n>>m;
int u,v,w;
init_floyd();
for(int i=1;i<=m;i++)
{
cin>>u>>v;
cin>>mp[u][v];
}
floyd();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<mp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
SPFA
在SPFA中 同一个点可能进出队列多次
即一个点被改进后会再次改进其他点
SPFA适用于存在负环的情况
存在负环 ——某个点入队次数超过N
不存在负环 ——得出最短路
需要注意的是，以 S 点为源点跑 SPFA 算法时，如果没有给出存在负环的结果，只能说明从 S 点出发不能抵达一个负环，而不能说明图上不存在负环。
int n,m;//n个节点 m条边
int s;//起点
int dis[N],num[N];
bool vis[N];
struct node{
int to,w,next;
}edge[N];
int head[N];
int cnt;
void init()
{
for(int i=1;i<=n;i++)
head[i]=-1,dis[i]=Inf;
cnt=0;
}
void add(int u,int v,int w)//加边过程
{
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
bool SPFA(int s)
{
queue<int> q;
memset(dis,0x3f,sizeof(dis));
memset(num,0,sizeof(num));
memset(vis,false,sizeof(vis));
bool f=1;
q.push(s);
vis[s]=1;
dis[s]=0;
num[s]++;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(!vis[v])
{
q.push(v);
vis[v]=1;
num[v]++;
}
if(num[v]>n)
{
f=0;
break;
}
}
}
if(!f)break;
}
return f;
}
int main()
{
cin>>n>>m;
init();
int u,v,w;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,-w);
}
if(SPFA(1))cout<<dis[n];
else cout<<"存在负环！";
return 0;
}
dijkstra
Dijkstra 是一种求解 非负权图 上单源最短路径的算法。
过程
将结点分成两个集合：已确定最短路长度的点集（记为 S 集合）的和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。
初始化 dis(s)=0，其他点的 dis 均为 正无穷。
然后重复这些操作：
从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。
对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。
直到 T 集合为空，算法结束。
点击查看代码
int n,m;//n个节点 m条边
int dis[N];
bool vis[N];
int cnt;
struct node{
int to,w,next;
}edge[N];
int head[N];
struct priority{
/*
值得注意的是
因为下文有直接赋值的语句
所以顺序尽量保持原样
*/
int ans;//该点对应的dis值
int id;//该点编号
bool operator <(const priority &x)const{
return x.ans<ans;
}//运算符重载
};
priority_queue<priority> q;
void init()
{
for(int i=1;i<=n;i++)
{
head[i]=-1;
}
cnt=0;
}
void add(int u,int v,int w)//加边过程
{
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dijkstra(int s)
{
for(int i=1;i<=n;i++)
{
dis[i]=Inf;
vis[i]=0;
}
dis[s]=0;
q.push((priority){0,s});//‘直接赋值的语句’
while(!q.empty())
{
priority temp=q.top();
q.pop();
int u=temp.id;
if(!vis[u])
{
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
q.push((priority){dis[v],v});
}
}
}
}
}
int main()
{
cin>>n>>m;
int u,v,w;
init();
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
}
int s;
cin>>s;
dijkstra(s);
for(int i=1;i<=n;i++)
{
cout<<dis[i]<<" ";
}
return 0;
}