最短路径算法
Floyed
PS: 能求带负边图, 但不能带负权回路
可以求出任意两点之间的最短路径
主代码:
- for(k=1;k<=n;k++)
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- if(i!=j&&j!=k&&i!=k)
- dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
- dijstra
PS: 不支持负边
求单源最短路径, 即起点只有一个
主代码:
- #include<iostream>
- #include<cstring>
- #define maxn 9999999
- using namespace std;
- int f[101][101];
- int n,m,x,y,s;
- int pre[101];// 记录前驱
- int to[101];// 从起点到当前节点的距离
- int v[101];// 是否访问过
- int main()
- {
- cin>>n>>m;
- memset(f,maxn,sizeof(f));
- for(int i=1;i<=m;i++)
- {
- cin>>x>>y>>s;
- f[x][y]=f[y][x]=s;
- }
- for(int i=2;i<=n;i++)
- {
- to[i]=f[1][i];// 从第一个点到每个点的初始距离
- if(f[1][i]!=maxn)// 如果被修改前驱就是第一个点
- pre[i]=1;
- }
- v[1]=1;
- for(int i=2;i<=n;i++)
- {
- int minn=maxn;
- int k=0;
- for(int j=2;j<=n;j++)
- if(v[i]==0&&to[i]<minn)// 如果没被标记过且小于最小值就替换
- {
- minn=to[i];
- k=j;
- }
- v[k]=1;// 找到了当前最短路
- for(int j=1;j<=n;j++)
- if(to[k]+f[k][j]<to[j])// 从当前最短路找下一条最短路
- to[j]=to[k]+f[k][j];
- }
- }
- SPFA
用 (循环) 队列优化的 Bellman-Ford
PS: 支持负边, 但不支持负环回路(如果回路只走一次就行)
team[]为队列
exist[]为一个点是否在队列中
dis[i]记录从起点到 i 的最短距离
w[i][j]表示从 i 到 j 的长度
pre[]前驱
- do
- {
- head++;
- exist[u]=0;
for 枚举所有链接的点
- if(dis[v]>dis[u]+w[u][v])
- {
- dis[v]=dis[u]+w[u][v];
- pre[v]=u;
- if(exist[v]==0)
- {
- exist[v]=1;
- tail++;
- team[tail]=v;
- }
- }
- }
- while(head<tail)
一个例题加深理解
例题: 洛谷 P3371 单源最短路径模板
https://www.luogu.org/problemnew/show/P3371
此处运用 SPFA + 链式前向星
- #include<iostream>
- using namespace std;
- int exist[500010];
- int team[2000000];
- int dis[500010];
- int head[500010];
- int n,m,s;
- int x,y,z;
- int cnt;
- int t=0,w=1;
- struct edge
- {
- int next;
- int to;
- int w;
- }edge[2500010];
- void add(int u,int v,int w)
- {
- edge[++cnt].w=w;
- edge[cnt].to=v;
- edge[cnt].next=head[u];
- head[u]=cnt;
- }
- int main()
- {
- cin>>n>>m>>s;
- for(int i=1;i<=n;i++)
- dis[i]=2147483647;
- for(int i=1;i<=m;i++)
- {
- cin>>x>>y>>z;
- add(x,y,z);
- }
- dis[s]=0;
- team[1]=s;
- while(t<w)
- {
- t++;
- int u=team[t];//u 等于入队的点
- exist[u]=0;
- for(int i=head[u];i!=0;i=edge[i].next)//i 从每个点能到的最后一条遍循环到第一条边
- {
- int v=edge[i].to;//v 等于每条遍的后面那个点
- if(dis[v]>dis[u]+edge[i].w)// 如果到这条遍后面的点距离比到这条边前面点加上边的权值小
- {
- dis[v]=dis[u]+edge[i].w;
- if(!exist[v])
- {
- w++;
- exist[v]=1;
- team[w]=v;
- }
- }
- }
- }
- for(int i=1;i<=n;i++)
- cout<<dis[i]<<" ";
- }
来源: http://www.bubuko.com/infodetail-2676576.html