[图算法之单源带负边的最短路径]Bellman-ford算法与spfa算法

Myth丶恋晨 2021-09-28 10:20 240阅读 0赞

### 图算法之单源带负边的最短路径 ###

*  前言
 *  Bellman-ford算法
 *  spfa算法
 *  例题

# 前言 #

不带负边的单源最短路径算法可以用Dikstra算法，但是带负边的最短路径算法需要使用Bellman-ford算法，以及其优化的 spfa算法

# Bellman-ford算法 #

假设一条点s到点t的最短路径为  
 s − > u 1 − > u 2 − > u 3 − > . . . − > u k − > t s->u\_1->u\_2->u\_3->...->u\_k->t s−>u1−>u2−>u3−>...−>uk−>t  
如果执行更新操作序列按照  
 ( s , u 1 ) 、 ( u 1 , u 2 ) 、 ( u 2 , u 3 ) 、 . . . 、 ( u k , t ) (s,u\_1)、(u\_1,u\_2)、(u\_2,u\_3)、...、(u\_k,t) (s,u1)、(u1,u2)、(u2,u3)、...、(uk,t)  
的顺序进行（即先更新 d i s ( u 1 ) dis(u\_1) dis(u1)，再更新 d i s ( u 2 ) dis(u\_2) dis(u2)…），那么到达t的距离将被正确的设定。

然而如果预先不知道所有的最短路径，又应该如何保证按照正确的顺序更新了正确的边呢？

解决方案：  
更新所有的边，每条边更新 ∣ V ∣ − 1 |V|-1 ∣V∣−1次。时间复杂度为O(|V|\*|E|)  
因为每次更新至少有一个点(即有一个 d i s ( i ) dis(i) dis(i))被正确设置了最短路径，那么进行|V|-1次，就可以设置好所有的边。

伪代码：

for all u∈V：
    	dis(u)= ∞
    	prev(u)=null;
    
    dist(s)=0;
    
    repeat |V|-1 times:
    	for all e∈E:
    		update(e)

update伪代码

procedure update((u,v)∈E)
    dist(v)=min{ dist(v),dist(i)+l(u,v)}

整合C代码

#include<bits/stdc++.h>
    const int INF = 99999999;
    using namespace std;
    int main()
    { 
        int u[100] , v[100] , w[100] , dis[100] , n , m ;
        //U[i]代表起始点，V[i]代表终点，w[i]代表权重
        cin>>n>>m; //顶点数和边数
    
    	//输入边
        for(int i = 1 ; i <= m ; i ++)
        { 
            cin>>u[i] >> v[i] >> w[i];
        }
    
    	//初始化
        for(int i = 1 ; i  <= n ; i ++)
       		dis[i] = INF;
        dis[1] = 0;
    
    	//更新
        for(int k = 1 ; k <= n - 1 ; k ++)
            for(int i = 1 ; i <= m ; i ++)
                if(dis[v[i]] > dis[u[i]] + w[i])
                    dis[v[i]] = dis[u[i]] + w[i];
        return 0 ;

# spfa算法 #

[参考博客入口][Link 1]

*  队列+松弛操作  
    读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d\[v\]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队，这样不断从队列中取出顶点来进行松弛操作。

以此循环，直到队空为止就完成了单源最短路的求解。

*  算法过程  
    设立一个队列用来保存待优化的顶点，优化时每次取出队首顶点 u，并且用 u 点当前的最短路径估计值dis\[u\]对与 u 点邻接的顶点 v 进行松弛操作，如果 v 点的最短路径估计值dis\[v\]可以更小，且 v 点不在当前的队列中，就将 v 点放入队尾。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。
 *  检测负权回路  
    方法：如果某个点进入队列的次数大于等于 n，则存在负权回路，其中 n 为图的顶点数。

#include<iostream> 
    #include<queue>
    #include<stack>
    using namespace std;
     
    int matrix[100][100];  //邻接矩阵
    bool visited[100];     //标记数组
    int dist[100];         //源点到顶点i的最短距离
    int path[100];         //记录最短路的路径
    int enqueue_num[100];  //记录入队次数
    int vertex_num;        //顶点数
    int edge_num;          //边数
    int source;            //源点
    
    //返回true成功更新所有顶点，返回false
    bool SPFA()
    { 
        memset(visited, 0, sizeof(visited));
        memset(enqueue_num, 0, sizeof(enqueue_num));
        for (int i = 0; i < vertex_num; i++)
        { 
            dist[i] = INT_MAX;
            path[i] = source;
        }
     
        queue<int> Q;
        Q.push(source);
        dist[source] = 0;
        visited[source] = 1;
        enqueue_num[source]++;
        while (!Q.empty())
        { 
            int u = Q.front();
            Q.pop();
            visited[u] = 0;
            for (int v = 0; v < vertex_num; v++)
            { 
                if (matrix[u][v] != INT_MAX)  //u与v直接邻接
                { 
                    if (dist[u] + matrix[u][v] < dist[v])
                    { 
                        dist[v] = dist[u] + matrix[u][v];
                        path[v] = u;
                        if (!visited[v])
                        { 
                            Q.push(v);
                            enqueue_num[v]++;
                            if (enqueue_num[v] >= vertex_num)
                                return false;
                            visited[v] = 1;
                        }
                    }
                }
            }
        }
        return true;
    }

# 例题 #

[POJ-1860–Currency Exchange][POJ-1860_Currency Exchange]

[解题][Link 2]

#include<iostream>
    #include<queue>
    #include<string.h>
    using namespace std;
    #define MAXN 105
    #define INF 1e9
    
    double rate[MAXN][MAXN];
    double com[MAXN][MAXN];
    
    int n, m, source;
    double value; // 货币种数，地点个数，s是种类，v价值 
    double dis[MAXN];
    bool vis[MAXN];
    int cnt[MAXN];
    
    bool spfa(){ 
    	queue<int> q; //存放节点 
    	while(!q.empty()){ 
    		q.pop();
    	}
    	
    	q.push(source);
    	vis[source]=1;
    	dis[source]=value;
    	
    	while(!q.empty()){ 
    		int f=q.front(); q.pop();		
    		vis[f]=0;
    		
    		//对每条边进行更新 
    		for(int i=1;i<=n;i++){ 
    			if(rate[f][i]!=INF && dis[i]<(dis[f]-com[f][i])*rate[f][i]){ 
    				
    				dis[i]=(dis[f]-com[f][i])*rate[f][i];
    				
    				if(!vis[i]){ 
    					vis[i]=1;
    					q.push(i);
    				}	
    				cnt[i]++;
    				
    				if(dis[source]>value||cnt[i]>=10000){ 
    					return 1;
    				}
    				
    				
    			}
    				
    		}
    			
    	}
    	return 0;
    		 
    } 
    	
    
    
    int main(){ 
    	while(cin>>n>>m>>source>>value){ 
    	
    		
    		int a,b; // 货币对 
    		
    		for(int i=0;i<n;i++){ 
    			for(int j=0;j<n;j++){ 
    				if(i==j){ 
    					rate[i][j]=1;
    					com[i][j]=0;
    				}
    				com[i][j]=rate[i][j]=INF;
    			}
    		}
    		
    		memset(vis,0,sizeof(vis));
    		memset(dis,0,sizeof(dis));
    		memset(cnt,0,sizeof(cnt));
    		
    		for(int i=0;i<m;i++){ 
    			cin>>a>>b;
    			
    			cin>>rate[a][b];
    			cin>>com[a][b];
    		
    			cin>>rate[b][a];
    			cin>>com[b][a];
    			
    		}//输入
    		
    		if(spfa()){ 
    			cout<<"YES"<<endl;
    			
    		}	
    		else{ 
    			cout<<"NO"<<endl;
    		}
    	}
    }

[Link 1]: https://www.cnblogs.com/xzxl/p/7246918.html
[POJ-1860_Currency Exchange]: http://poj.org/problem?id=1860
[Link 2]: https://blog.csdn.net/meituanwaimai/article/details/78106229