Bellman-Ford算法和SPFA算法以及Floyd算法学习心得

本文主要是介绍Bellman-Ford算法和SPFA算法以及Floyd算法学习心得，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于BF算法，我们主要是用于解决Dijkstra算法不能解决的问题，我们之前说到，Dijkstra算法的使用范围是结点之间的边权为正数的情况。所以BF算法可以解决边权为负的情况。
我们考虑环的问题，我们可以知道，如果某个点经过一系列的点后回到自身后，如果边权之和为正的话，则称为正环，为0则为零环，为负则为负环。对于正环和零环的情况，我们可以知道不会影响最短路径的取值，但是如果出现负环，我们的算法就很可能受到影响。但是，因为我们考虑的是有向图的情况，如果我们从源点出发不能通过该负环到达我们要源点自身，那么最短路径的求法还是不会受到影响的。
下面这种的是Bellman—Ford算法，其实这种的和Dijkstra算法相比就是这个多了一个最外层的n-1次循环。

bool Bellman(int s){fill(d,d+maxn,INF);fill(num,num+maxn,0);fill(w,w+maxn,0);d[s]=0;w[s]=weight[s];num[s]=1;for(int i=0;i<n-1;i++){for(int u=0;u<n;u++){for(int j=0;j<Adj[u].size();j++){int v=Adj[u][j].v;int dis=Adj[u][j].dis;if(d[u]+dis<d[v]){w[v]=w[u]+weight[v];d[v]=d[u]+dis;num[v]=num[u];pre[v].clear();pre[v].insert(u);}else if(d[u]+dis==d[v]){if(w[u]+weight[v]>w[v]){w[v]=w[u]+weight[v];}pre[v].insert(u);num[v]=0;set<int>::iterator it=pre[v].begin();for(;it!=pre[v].end();it++){num[v]+=num[*it];}}}}}for(int u=0;u<n;u++){for(int j=0;j<Adj[u].size();j++){int v=Adj[u][j].v;int dis=Adj[u][j].dis;if(d[u]+dis<d[v]){return false;}}}return true;
}

但是，我们会发现，BF算法的时间复杂度十分不理想，O(VE)，我们可以注意到，当我们的u结点发生改变时，我们的从u结点可以到达的v结点才可能会发生改变，那么，我们就可以考虑建立一个队列，这个队列是存放那些改变的结点，如果我们的u发生了改变的话，那么我们的v就要放入队列里面。我们有邻接表的写法，然后开一个num数组来记录每个结点入队的次数，如果某一个结点入队的次数超过了n-1次的话，就说明图存在负环，返回false
。这样的话，我们就可以不要再将父结点u没有改变的那些点后面的进行改变了，从而达到了优化的目的。

const int maxn=2010;
struct Node{int v,dis;
};
vector<Node> Adj[maxn];
int num[maxn],d[maxn];
bool vis[maxn];bool Bellman(int s){memset(vis,false,sizeof(vis));memset(num,0,sizeof(num));d[s]=0;queue<Node> q;num[s]++;vis[s]=true;while(!q.empty()){int u=q.front();q.pop();vis[u]=true;for(int j=0;j<Adj[u].size();j++){int v=Adj[u][j].v;int dis=Adj[u][j].dis;if(d[u]+dis<d[v]){   //需要更新d[v]=d[u]+dis;if(!vis[v]){q.push();vis[v]=true;num[v]++;if(num[v]>=n)  return false;  //如果某个结点入队的次数超过n-1次}}}}return true;
}

Floyd算法
之前我们讲的算法主要的针对的是单源结点的最短距离，而这个算法主要针对的是全源最短路径的情况，也就是求出任意两个点之间的最短路径的问题
由于时间复杂度为O(n^3),那么我们建议用邻接矩阵来进行存储。我们还是以一个中介结点k,如果i，k之间的距离和k，j之间的距离之和小于i，j之间的距离。那么我们就可以更新我们的i，j之间的距离。三重循环i,j,k,那么我们如何分配我们这三个循环的位置呢？也就是我们把作为中间节点的那一层循环放入最外层，因为我们要先对里面的小区间之间进行更新，然后从里面往外面进行更新。

const int maxn=2020;
const int INF=1000000000;int dis[maxn][maxn];void Floyd(){for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){dis[i][j]=dis[i][k]+dis[k][j];}}}}
}