大家好,又见面了,我是你们的朋友全栈君。
熟悉的最短路算法就几种:bellman-ford,dijkstra,spfa,floyd。
bellman-ford可以用于边权为负的图中,图里有负环也可以,如果有负环,算法会检测出负环。
时间复杂度O(VE);
dijkstra只能用于边权都为正的图中。
时间复杂度O(n2);
spfa是个bellman-ford的优化算法,本质是bellman-ford,所以适用性和bellman-ford一样。(用队列和邻接表优化)。
时间复杂度O(KE);
floyd可以用于有负权的图中,即使有负环,算法也可以检测出来,可以求任意点的最短路径,有向图和无向图的最小环和最大环。
时间复杂度O(n3);
任何题目中都要注意的有四点事项:图是有向图还是无向图、是否有负权边,是否有重边,顶点到自身的可达性。
1、Dijkstra(单源点最短路)
这个算法只能计算单元最短路,而且不能计算负权值,这个算法是贪心的思想, dis数组用来储存起始点到其他点的最短路,但开始时却是存的起始点到其他点的初始路程。通过n-1遍的遍历找最短。每次在剩余节点中找dist数组中的值最小的,加入到s数组中,并且把剩余节点的dist数组更新。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 0x3f3f3f3f;
const int p = 1005;
int a[p][p];//存放点与点的距离
int dist[p];//源点到各个点的最短距离
int pre[p];//计算过的点
int s[p];//判断是否已经加入pre,是否已访问
int n,m;
void Dijkstra(int v)
{
int i,j;
for(i = 0;i < n;++i)
{
if(i != v)
{
dist[i] = a[v][i];
}
s[i] = false;
}
s[v] = true;
dist[v] = 0;
pre[0]=v;
//对各个数组进行初始化
for(i = 0;i < n;++i)
{
int minset = MAXN;
int u = v;
for(j = 0; j < n;++j)
{
if(!s[j] && dist[j] < minset)
//找到剩余节点中最小的节点
{
u = j;
minset = dist[u];
}
}
s[u] = true;
//将节点标记为以访问,相当于加入s数组中
for(j = 0;j < n;++j)
{
if(!s[j] && a[u][j] < MAXN)
//a[u][j] < MAXN指更新u的可达点
{
if(dist[u] + a[u][j] < dist[j])
{
dist[j] = dist[u] + a[u][j];
pre[j] = u;
//储存得出最短路径的前一个节点,用于路径还原
}
}
}
}
}
int main()
{
int t;
cin>>t;
while(~scanf("%d %d",&n,&m))
{
memset(a,MAXN,sizeof(a));
memset(dist,MAXN,sizeof(dist));
int i,j;
for(i = 0;i < m;++i)
{
int x,y,d;
scanf("%d %d %d",&x,&y,&d);
a[x-1][y-1]=d;
a[y-1][x-1]=d;
}
//int v;
//scanf("%d",&v);
Dijkstra(0);
for(int i = 0;i < n;++i)
{
printf("%d ",dist[i]);
}
printf("\n");
/*for(int i = 0;i < n;++i) { printf("%d ",s[i]); } printf("\n"); for(int i = 0;i < n;++i) { printf("%d ",pre[i]); } printf("\n");*/
}
return 0;
}
Floyd:
floyd算法是非常强大的,可以处理不少问题,复杂度是O(n^3)的,下面解析一下这个算法
不少人可能刚接触floyd的时候非常容易把它写错,错误的写法就是三层循环的从外到内的变量分别为i,j,k,正确的写法应该是k,i,j。写错的原因是不理解floyd算法造成的,那么为什么从顺序是k,i,j呢?
其实floyd的算法本质是个动态规划!dp[k][i][j]代表i到j的中间节点(不包括i和j)都在区间[1,k]时,i到j的最短路。算法的最外层循环是个从小到大枚举k的过程,当最外层刚刚进入第k次循环的时候,我们已经得到了所有点对的dp[k-1][][]的值,也就是所有点对(i,j)的i到j的中间节点都在[1,k-1]区间的i到j的最短路。那么对任意的点对(i,j),如果他俩的最短路经过k点,则dp[k][i][j]=dp[k-1][i][k]+dp[k-1][k][j];如果不经过k点,则dp[k][i][j]=dp[k-1][i][j]。所以当我们求dp[k][][]的时候,要保证所有的dp[i-1][][]都求出来了,因此,最外层循环是k。
每一层都是有上一层决定,不会受这一层影响,所以可以利用滚动数组优化内存空间,将k去除掉
任意节点i到j的最短路径不外乎两种可能:1、直接从i到j;2、从i经过若干个节点k到j。Dis(i,j)表示节点i到j最短路径的距离,对于每一个节点k,检查Dis(i,k)+Dis(k,j)小于Dis(i,j),如果成立,Dis(i,j) = Dis(i,k)+Dis(k,j);遍历每个k,每次更新的是除第k行和第k列的数。(十字交叉法,可百度)。
floyd能做很多事情,下面简单说两个,求有向图的最小环或者最大环(顶点数>=2),求无向图的最小环(顶点数>=3)。
先说求有向图最小环(最大环略)。有两种方法可以求,一种是设定g[i][i]为无穷大,这样最后找所有的g[i][i]里的最小值就行;另一种是正常做floyd,然后对每个点对(i,j),求g[i][j]+dp[n][j][i]的最小值,这样的原理是最小环如果存在的话,那么可以枚举一个这个环里的边i->j,那么包含这条边的最小的环一定是i->j和dp[n][j][i]构成的最短路。
无向图的最小环做法和有向图不一样,是因为无向边可能会被用两次导致出错,举例说就是:枚举了一条边i->j,然后其与dp[n][j][i]的和作为一个结果,但是如果j到i的最短路就是边j->i的话,那么我们找的环其实只是一条边而已,这样的结果显然是错误的。正确的做法是先判断最小环再更新最短路。(为什么?)
因为会出现重边的现象,所以一个环一定至少有三个点,所以每次先判断最小环,因为k必须是未用过的,此时的dist[i][j]是遍历了k-1次的最短路,用完判断了再去更新k对应的最短路。每次比较dist[i][j]+
g[i][k]+g[k][j]的最小值。k—>i————>j—->k;这样一直保证环是三个点。
hdu1599(用Floyd求无向图的最小环)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
const int p = 105;
int dist[p][p];
int mp[p][p];
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
int i,j,k;
for(i = 0;i < n;++i)
{
for(j = 0;j < n;++j)
{
dist[i][j] = MAXN;
mp[i][j] = MAXN;
}
}
for(i = 0;i < m;++i)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(c < mp[a-1][b-1])
dist[a-1][b-1]=dist[b-1][a-1]=mp[b-1][a-1]=mp[a-1][b-1]=c;
}
int ans = MAXN;
for(k = 0;k < n;++k)
{
for(i = 0;i < n;++i)
{
for(j = i+1;j < n;++j)
//这里用i+1,防止i,j是不同的两个点
{
if(ans > dist[i][j] + mp[i][k] + mp[k][j])
{
ans = dist[i][j] + mp[i][k] + mp[k][j];
}
}
}
for(i = 0;i < n;++i)
{
for(j = 0;j < n;++j)
{
if(dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
if(ans == MAXN)
printf("It's impossible.\n");
else
printf("%d\n",ans);
}
return 0;
}
Floyd的模板:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 0x3f3f3f3f;
const int p = 1005;
int dist[p][p];
int path[p][p];
int mp[p][p];
int n,m;
int Floyd()
{
int i,j,k;
for(i = 0;i < n;++i)
{
for(j = 0;j < n;++j)
{
dist[i][i]=0;
mp[i][i]=0;
}
}
int ans = MAXN;
for(k = 0;k < n;++k){
for(i = 0;i < n;++i)
{
for(j = 0;j < n;++j)
{
if(dist[i][k] + dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int i,j;
memset(path,-1,sizeof(path));
memset(dist,MAXN,sizeof(dist));
memset(mp,MAXN,sizeof(mp));
scanf("%d %d",&n,&m);
for(int i = 0;i < m;++i)
{
int x,y,d;
scanf("%d %d %d",&x,&y,&d);
dist[x][y]=d;
dist[y][x]=d;
mp[x][y]=d;
mp[y][x]=d;
}
printf("%d\n",Floyd());
for(i = 0;i < n;++i)
{
for(j = 0;j < n;++j)
{
printf("%d ",dist[i][j]);
}
cout<<endl;
}
for(i = 0;i < n;++i)
{
for(j = 0;j < n;++j)
{
printf("%d ",path[i][j]);
}
cout<<endl;
}
}
return 0;
}
Bellman-Ford:
适用范围:1、单源最短路径(从源点到其他所有点v);
2、有向图&无向图;
3、边权可正可负
4、差分约束系统
图G(v,e),源点s,数组Distant[i]记录了从源点s到顶点i的路径长度,循环执行至多n-1次,n为顶点数。
对每一条边e(u,v),如果Distant[u]+w[u,v]小于Distant[v],则Distant[v] = Distant[u]+w(u,v);
每一次循环都会至少更新一个点,所以才会出现至多循环n-1次,一次更新是指用所有节点进行一次松弛操作,(为什么会出现循环一次都能至少确定一个节点的最短距离?)
因为:1、将所有节点分为两类:已知最短距离的节点和剩余节点。
2、这两类节点满足这样的性质:已知最短距离的节点的最短距离值都比剩余节点的最短路值小。
3、易知到剩余节点的路径一定会经过已知节点。
4、而从已知节点连到剩余节点的所以边中的最小的那个边,这条边所更新后的剩余节点就一定是确定的最短距离,从而多找到了一个能确定最短距离的节点(不用知道它是哪个节点)。
实现过程的三步:1、初始化所有的点,每一个点保存一个值,表示源点到这个点的距离其他点的值设为无穷大。
2、进行循环,从1到n-1,进行松弛计算。
3、遍历所有边,如果的d[v]大于d[u]+w(u,v)存在,则有从源点可达的权为负的回路。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 0x3f3f3f3f;
const int p = 100005;
typedef struct Graph{
int u,v,cost;
};
//有向图
Graph edge[p];//边表
int pre[p];
int dis[p];
int n,m,v;//点数,边数,源点
bool BellmanFloyd()
{
int i,j;
for(i = 1;i <= n;++i)//最多进行n-1次更新
{
for(j = 0;j < m;++j)//每次遍历一下边表,至少找出一个点的最短路径
{
if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost)
{
dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;
}
}
}
bool flag = true;
for(i = 0;i < m;++i)//判断负环
{
if(dis[edge[i].v]>dis[edge[i].u]+edge[i].cost)
{
flag = false;
break;
}
}
return flag;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
int i,j;
memset(dis,MAXN,sizeof(dis));
memset(pre,-1,sizeof(pre));
for(i = 0;i < m;++i)
{
scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].cost);
}
dis[1] = 0;
pre[1] = 1;
BellmanFloyd();
for(i = 1;i <= n;++i)
{
printf("%d ",dis[i]);
}
printf("\n");
}
return 0;
}
介绍SPFA之前先介绍一个图的存储方式:邻接表(可以用来优化算法)
可以用数组实现,因为本人不喜欢用指针实现,所以也没尝试。
对于图来说,邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式:邻接表(Adjacency List),即数组与链表相结合的存储方法。
邻接表的处理方法是这样的。
1、图中顶点用一个一维数组存储,另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。
2、图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi的边表,有向图称为顶点vi作为弧尾的出边表。
用数组实现
next[i]存储的是“编号为i的边”的“前一条边”的编号。
可通过next找到以某一个顶点为起始点的所有边。
SPFA是一种求单源最短路的算法(Bellman-ford的优化版)
算法中需要用到的主要变量
int n; //表示n个点,从1到n标号
int s,t; //s为源点,t为终点
int d[N]; //d[i]表示源点s到点i的最短路
int p[N]; //记录路径(或者说记录前驱)
queue q; //一个队列,用STL实现,当然可有手打队列,无所谓
bool vis[N]; //vis[i]=1表示点i在队列中 vis[i]=0表示不在队列中
几乎所有的最短路算法其步骤都可以分为两步
1.初始化
2.松弛操作
初始化: d数组全部赋值为INF(无穷大);p数组全部赋值为s(即源点),或者赋值为-1,表示还没有知道前驱点, 然后d[s]=0; 表示源点不用求最短路径,或者说最短路就是0。将源点入队;(另外记住在整个算法中有顶点入队了要记得标记vis数组,有顶点出队了记得消除那个标记)
队列+松弛操作
读取队头顶点u,并将队头顶点u出队(记得消除标记);将与点u相连的所有点v进行松弛操作,如果能更新估计值(即令d[v]变小),那么就更新,另外,如果点v没有在队列中,那么要将点v入队(记得标记),如果已经在队列中了,那么就不用入队
以此循环,直到队空为止就完成了单源最短路的求解
SPFA可以处理负权边
定理: 只要最短路径存在,上述SPFA算法必定能求出最小值。
证明:
每次将点放入队尾,都是经过松弛操作达到的。换言之,每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路,所以每个结点都有最短路径值。因此,算法不会无限执行下去,随着d值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。(证毕)
期望的时间复杂度O(ke), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2。
判断有无负环:
如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)
算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MAXN = 20005;
const int MINX = 1005;
int u[MAXN];
int v[MAXN];
int w[MAXN];
int first[MINX];
int ne[MAXN];
int d[MINX];
bool vis[MINX];
int p[MINX];
queue<int>que;
void spfa_bfs()
{
int i,j;
while(!que.empty())
{
int k = que.front();
que.pop();
vis[k] = 0;
for(int x = first[k];x != -1;x = ne[x])
{
int y = v[x];
if(d[y] > d[k] + w[x])
{
d[y] = d[k] + w[x];
p[y] = x;
if(!vis[y]){
vis[y] = 1;
que.push(y);
}
}
}
}
}
int main()
{
int n,m,s,t;
while(~scanf("%d %d %d",&n,&m,&s))
{
int x,y,z;
int i,j;
memset(ne,-1,sizeof(ne));
memset(first,-1,sizeof(first));
memset(vis,0,sizeof(vis));
memset(d,inf,sizeof(d));
memset(p,-1,sizeof(p));
d[s] = 0;
vis[s] = 1;
p[s] = s;
que.push(s);
for(i = 1;i <= m;++i)
{
scanf("%d %d %d",&x,&y,&z);
u[i] = y;
v[i] = x;
w[i] = z;
if(first[y] == -1){
first[y] = i;
}
else
{
ne[i] = first[y];
first[y] = i;
}
}
spfa_bfs();
/*for(i = 1;i <= m;++i) { printf("%d %d %d %d %d\n",u[i],v[i],w[i],first[i],ne[i]); } for(i = 1;i <= n;++i) { printf("%d ",d[i]); } cout<<endl;*/
scanf("%d",&t);
int ptr;
int mx = inf;
for(j = 0;j < t;++j)
{
scanf("%d",&ptr);
mx = (mx > d[ptr])?d[ptr]:mx;
}
if(mx == inf)
printf("-1\n");
else
printf("%d\n",mx);
}
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136217.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...