最短路 dij floy spfa

例题 hdu1874 https://blog.csdn.net/murmured/article/details/18568657

一、Dijkstra

不可以算权值为负数的图

Dijkstra单源最短路算法，即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。

 使用邻接矩阵的时间复杂度为O(n^2),用优先队列的复杂度为O((m+n)logn)近似为O(mlogn)

为朴素版本：

http://blog.51cto.com/ahalei/1387799

还有一个 堆优化+邻接表（链式前向星）优化版本：

const int maxn=1000005;
const int inf=0x3f3f3f3f;
struct Edge{
	int v,w;//w为距离 
	int next;
};
Edge edge[maxn];//边编号  从1开始   
struct qnode{    //堆优化 
     int u;	//起点 
     int w;//距离
     
   qnode(int u=0,int w=0):u(u),w(w){}//结构体重载 
  
	bool operator < (const qnode& a) const{
	return w>a.w;
	} 
};
long long dis[maxn];
int head[maxn];
bool vis[maxn];
int x[maxn],y[maxn],z[maxn];
int n,m;
int size; 
void add_edge(int u,int v,int w){//邻接表加边 
	  edge[size].v=v;
	  edge[size].w=w;
	  edge[size].next=head[u];
	  head[u]=size;
	  size++; 
}
void dijkstra(int s){
	priority_queue<qnode>q;
	while(!q.empty())
	q.pop();
    q.push(qnode(s,0));
	dis[s]=0;

	while(!q.empty()){
		qnode t=q.top();
		q.pop();
		int u=t.u;
		if(vis[u])continue;
		vis[u]=true;//找到一个点就标记一次 
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].v;
			int w=edge[i].w; 
			if(!vis[v]&&dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(qnode(v,dis[v]));//存到队堆里会自动利用堆 进行排序； 
			} 
		}	
	}
}

{邻接表：http://blog.51cto.com/ahalei/1391988 

其实我咋感觉 领接表 与 链式前向星一样啊

 

二、floyd

可以解决传递闭包问题

可以处理边是负数的情况，判断图中是否为有负圈，检查是否存在dis[i][i]是否为负数

处理回路（环）就看dis[i][i]。（Floyd 和 bellman-ford 都可已处理环）

任意两点间的短路问题

 

三、SPFA（bellman-ford）

单源最短路径    可以判断负环

bellman-ford算法的基本思想是，对图中除了源顶点s外的任意顶点u，依次构造从s到u的最短路径长度序列dist[u],dis2[u]……dis(n-1)[u]，其中n是图G的顶点数，dis1[u]是从s到u的只经过1条边的最短路径长度，dis2[u]是从s到u的最多经过G中2条边的最短路径长度……当图G中没有从源可达的负权图时，从s到u的最短路径上最多有n-1条边。因此，dist(n-1)[u]就是从s到u的最短路径长度，显然，若从源s到u的边长为e(s,u)，则dis1[u]=e(s,u).对于k>1，dis（k)[u]满足如下递归式，dis(k)[u]=min{dis(k-1)[v]+e(v,u)}.bellman-ford最短路径就是按照这个递归式计算最短路的。

bellman-ford算法    Bellman-ford 算法：一个具有n个顶点的图如果不存在环，则从顶点x,到顶点y，最多经过n-1条边（要考虑连通性，每个顶点最多经过 1 次），因此 x 到 y 的最短路 最多经过 n - 1 次松弛操作（就是更新长度）就应该出现，如果第 n 次松弛还可以得到最优，那么这个图就肯定是存在环了（直接用Dijkstra 就无法得到最优的，环的存在会影响最优解是否存在）。

SPFA的实现如下：用数组dis记录更新后的状态，cnt记录更新的次数，队列q记录更新过的顶点，算法依次从q中取出待更新的顶点v,按照dis(k)[u]的递归式计算。在计算过程中，一旦发现顶点K有cnt[k]>n，说明有一个从顶点K出发的负权圈，此时没有最短路，应终止算法。否则，队列为空的时候，算法得到G的各顶点的最短路径长度。

多次入队因为因为SPFA没有向迪杰斯塔拉算法那样，寻找dist[]的最小值，所以重复入队用所有结点来进行松弛，更新dis[]的最小值，因为这个点本身dis[]的变化，会影响到与之邻接的点，所以要重复入队。

判断负环代码如下（ 与不判断只差两行）

    bool spfa()    
    {    
        for(int i=0;i<=n;i++)    
            dis[i]=INF;    
        
        bool vis[MAXN]={0};    
        int cnt[MAXN]={0};    
        queue<int> q;    
        dis[0]=0;    
        vis[0]=true;    
        cnt[0]=1;    
        q.push(0);    
        
        while(!q.empty())    
        {    
            int cur=q.front();    
            q.pop();    
            vis[cur]=false;    
        
            for(int i=head[cur];i!=-1;i=e[i].next)    
            {    
                int id=e[i].to;    
                if(dis[cur] + e[i].val > dis[id])    
                {    
                    dis[id]=dis[cur]+e[i].val;    
                    if(!vis[id])    
                    {    
                        cnt[id]++;    
                        if(cnt[cur] > n)    //判断负环
                            return false;    //结束函数
                        vis[id]=true;    
                        q.push(id);    
                    }    
                }    
            }    
        }    
        return true;    
    }