最短路小结

单源最短路

dijkstra算法:只适用于没有负边权的图

算法流程:

  1.初始化dist[st]=0,其余dist的值设置为INF

  2.找出一个未被标记的,dist[x]最小的结点x,然后标记x

  3.扫描x的所有边,进行松弛  

  4.2.3步骤重复n-1次

int a[maxn][maxn],d[maxn],n,m;
bool v[maxn];
void dijkstra(){
    memset(d,0x3f,sizeof d);//dist数组 
    memset(v,0,sizeof v);//标记数组 
    d[1]=0;
    for(int i=1;i<n;i++){
        int x=0;
        for(int j=11;j<=n;j++)//第2步 
            if(!v[j] && (x==0 || d[j]<d[x])) x=j;
        v[x]=1;
        for(int y=1;y<=n;y++)//第3步 
            d[y]=min(d[y],d[x]+a[x][y]);
    }
}

以上算法复杂度n^2。主要在于每次重复第2步,现在用堆来优化,用loge(如果用普通的优先对列是loge,但是用斐波那契堆可以到logn)时间获取最小值

dijkstra+堆优化(优化第2步)

void dijkstra(){
    memset(d,0x3f,sizeof d); 
    memset(v,0,sizeof v);
    d[1]=0;
    q.push(make_pair(0,1));//起点入队
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(v[x])continue;//已经在集合里的点就不用再访问了 
        v[x]=1;
        for(int i=head[x];i!=-1;i=edge[i].nxt){
            int y=edge[i].to,z=edge[i].w;
            if(d[y]>d[x]+z){//把新的二元组插入堆中
                d[y]=d[x]+z;
                q.push(make_pair(-d[x],y));
            }
        } 
    } 
} 

为什么dij算法不能处理负边权:

   因为dij算法能够依次将点加入到集合中,已经加到集合中的点的dist就无法再变动。

   现在假设新加入的点是通过负边加入的,那么通过这条负边,其实有可能松弛集合中点的dist,但是已经规定了集合中的点无法更新,所以该算法无法成立(就是原来的贪心策略不成立了)

bell_man和spfa算法

bell_manford算法:单源最短路确定当且仅当边集合中所有边都满足三角形不等式,即图中任意一条边(x,y,z)都有d[x]+z>=d[y]

  1.扫描所有边(x,y,z),若d[y]>d[x]+z,则松弛

  2.重复上述步骤,若完成一轮扫描后没有进行松弛,则算法结束

算法中第i轮循环可以表示st经过最多i条边可以到达终点的最短路,显然最多n-1轮后st到所有点的最短路确定

因为第i轮中被松弛的点必定经过i条边,那么n-1轮中松弛的就是经过n-1条边的点,如果n轮还能松弛说明必定出现了环

和dij不同之处在于算法没有固定到某点的距离,而是不断进行松弛,也就是锁到各点的最短路到算法结束后才确定下来,因此可以处理dij无法处理的有负权边的情况

复杂度nm,算法最多执行n-1次,如果执行n-1次之后仍可以松弛,那么该图中有负环。

  证明:从st经过n条边到k,且比经过任何少于n条边到k的权值更小

     n条边中必定有一个环,那么,这个环必定是负环

spfa算法:队列优化的bellman_ford

  1.建立一个队列,里面有st

  2.取出头结点x,扫描其所有出边,松弛:若d[y]>d[x]+z,则更新d[y],同时,若y不在队列中,将y加入队列(如果y在队列中并且被松弛,说明y是在同一轮边的遍历中被松弛的)

  3.重复直到队列清空

能够保证需要更新的点都在队列中,当更新完成时队列就空了,相对于bellman_ford每次扫描所有边,spfa算法能够避免不需要的判断

对应于bellman_ford,每个点被松弛时入队,当一个点被入队n次时,则出现了负环

同时,一个点可能入队多次,但不会超过n-1次,否则就是有负环存在

int spfa(){
    memset(d,0x3f,sizeof d);
    memset(v,0,sizeof v);//v数组用来判断i是否在队列里 
    memset(cnt,0,sizeof cnt);//用来判断负环是否存在 
    d[1]=0,v[1]=1;
    q.push(1);
    while(!q.empty()){
        int x=q.front();q.pop();
        v[x]=0;
        for(int i=head[x];i!=-1;i=edge[i].nxt){
            int y=edge[i].to,z=edge[i].w;
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                if(v[y]==0)q.push(y),v[y]=1;
                if(++cnt[y]>n)return false; 
            }
        } 
    }
    return true;
}

 

原文地址:https://www.cnblogs.com/zsben991126/p/10466117.html