Lflame

K短路 --- Yen 算法

    资料:

    http://ycool.com/post/krb8pah

    http://ycool.com/post/ppswum7  这两篇都讲得很详细,是同一个人写的

    

    这是一个很强大的算法,其本质也是属于 A* 的。%%%听说有用可持久化堆来做 K 短路的可以做到 O(nlogn + mlogm + klogk),不过Yen算法在很多情况下还是够用了... (Orzzz 可是蒟蒻的我依然看了好久才看懂)

    Yen 算法是一种偏离算法,相当于每次在原有路径上,通过偏离,找到在原有路径的基础上次长的路径。


    状态中存储了偏离点dev,即这条路径被之前某条路径偏离得到时,不属于之前那条路径的第一个点。状态还存储了哪些边在之前偏离时被禁止了的。

    算法的开始,先求一遍 S 到 T 的最短路,作为初始状态的路径,为了契合定义,这个状态的dev为最短路径上第二个点,然后将其放入优先队列。每次从队首取出一个状态 sta,pop掉,然后在这个状态的路径上,从dev之前的一个点开始一直到 T 点(可以走重复点时,否则为T点之前的那个点)这些点中选取一个点 a,找到从点 a 出发通过其他边到达 T 点的最短路径。这时得到一个新的状态 sta',假设走了边 (a , b),则其 dev 为 b,并且要将边(a , b)放入这个状态的禁止边的vector中,并且若sta' 与 sta都是从同一个点偏离得到,那么需要将sta'的禁止边的vector拷贝入sta,最后将sta'放入优先队列。

    其中怎么找从点 a 出发通过其他边(即不是sta的禁止边的边)到达 T 点的最短路径呢 ? 如果题目允许走重复的点,那么直接预先处理出每个点到 T 的最短距离,找的时候for一遍点 a 的边,找到 w(a,b) + dis[b] 最小的点 b 即可。如果题目不允许走重复的点,那么我们将 sta 中 a 之前的点全部ban掉,再跑一遍最短路就可以了。


    bzoj1073这道题,是需要字典序最小的,那怎么办呢 ?

    我们将整个图的边反过来,可以发现每一条原来的 S-T路径都对应一条现在的 T-S 的路径,并且路径长度不变。然后做最短路时,存储一个 pre ,表示这个点的 dis 从哪个点更新过来,那么当dis[v] == dis[u] + w(u,v)时,判断 u 的字典序是否小于 pre[v],小于则更新pre[v]=u。 这样就保证每个点的前一个点的字典序尽量小,对应到反图之前的路径,就是每个点的后一个点的字典序尽量小,正好符合字典序最小的定义。


    代码 :

    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;

  

struct states

{

    vector<int> ban ; //偏离点的前一个点的边限制

    vector<int> path ; //存边

    int dev ; //表示偏离点的出边在path中的序号

    int t_len ;

};

  

struct Dijk_states

{

    int xh , t_dis ;

    Dijk_states(int _xh=0,int _t_dis=0){

        xh=_xh , t_dis=_t_dis ;

    }

};

  

priority_queue<Dijk_states> Dijk_que ;

priority_queue<states> que ;

int n,m,K,A,B ;

int first[10005],nexts[10005],to[10005],w[10005],from[10005],egnum ;

int dis[55] , pre[55] , INF , pre_eg[55];

int ban_eg[10005] , TTT , ban_p[55];

bool over[55] ;

  

//ban_p 是防止转移进来   over 是防止转移出去

  

bool operator<(const Dijk_states &a,const Dijk_states &b)

{

    return a.t_dis>b.t_dis ;

}

  

bool operator<(const states &a,const states &b)

{

    if(a.t_len==b.t_len){

        int len_a=a.path.size() , len_b=b.path.size() ;

        int t=min(len_a,len_b) ;

        for(int i=1;i<=t;++i){

            int ta=from[a.path[len_a-i]] , tb=from[b.path[len_b-i]];

            if(ta>tb)    return true ;

            if(ta<tb)    return false ;

        }

        return len_a>len_b ;

    }

    return a.t_len>b.t_len ;

}

  

void add_edge(int a,int b,int c)

{

    nexts[++egnum]=first[a] ;

    first[a]=egnum ;

    to[egnum]=b ;

    from[egnum]=a ;

    w[egnum]=c ;

}

  

void Dijkstra() //信息要在函数外先初始化

{

    while(!Dijk_que.empty()){

        Dijk_states tp=Dijk_que.top() ;

        Dijk_que.pop() ;

        if(over[tp.xh]) continue ;

        over[tp.xh]=true ;

        int a=tp.xh ;

        for(int i=first[a];i;i=nexts[i]){

            if(ban_eg[i]==TTT)  continue ;

            int b=to[i] ;

            if(ban_p[b]==TTT)   continue ;

            if(dis[b]==dis[a]+w[i] && pre[b]>a){

                pre[b]=a , pre_eg[b]=i ;

            }

            if(dis[b]>dis[a]+w[i]){

                dis[b]=dis[a]+w[i] ;

                pre[b]=a , pre_eg[b]=i ;

                Dijk_que.push(Dijk_states(b,dis[b])) ;

            }

        }

    }

}

  

void rev(states &a)

{

    reverse(a.path.begin(),a.path.end()) ;

}

  

void ext(const states &tp)

{

    int len=tp.path.size() ;

    for(int i=tp.dev-1;i<len;++i){ 

        ++ TTT ;

        while(!Dijk_que.empty()){

            Dijk_que.pop() ;

        }

        if(i==tp.dev-1){

            int l=tp.ban.size() ;

            for(int j=0;j<l;++j) ban_eg[tp.ban[j]]=TTT ;

        }

        ban_eg[tp.path[i]]=TTT ;

        memset(dis,0x3f,sizeof(dis)) ;

        memset(over,false,sizeof(over)) ;

        dis[B]=0 ;

        for(int j=0;j<=i;++j){

            ban_p[from[tp.path[j]]]=TTT ;

            if(j!=i) over[from[tp.path[j]]]=true ;

            int a=from[tp.path[j]] ;

            if(j){

                dis[a]=dis[from[tp.path[j-1]]]+w[tp.path[j-1]] ;

                pre_eg[a]=tp.path[j-1] , pre[a]=from[tp.path[j-1]];

            }

            if(j==i)    Dijk_que.push(Dijk_states(a,dis[a])) ;

        }

        Dijkstra() ;

        if(dis[A]==INF) continue ;

        int t=A;

        states tmp ;

        while(t!=B){

            tmp.path.push_back(pre_eg[t]) ;

            t=pre[t] ;

        }

        rev(tmp) ; tmp.dev=i+1 ;

        if(i==tp.dev-1) tmp.ban=tp.ban ;

        else tmp.ban.push_back(tp.path[i]) ; 

        tmp.ban.push_back(tmp.path[i]) , tmp.t_len=dis[A] ;

        que.push(tmp) ;

    }

    //可优化

}

  

void ss(){

    cout << que.size() << '\n';

}

  

void print()

{

    cout << que.top().t_len << '\n' ;

    int len=que.top().path.size() ;

    for(int i=0;i<len;++i){

        cout << from[que.top().path[i]] << ' ' ;

    }

    cout << A ;

    cout << '\n' ;

}

  

void solve()

{

    memset(dis,0x3f,sizeof(dis)) ;  

    memset(over,false,sizeof(over)) ;

    ++TTT ;

    INF=dis[0] ;

    dis[B]=0 , Dijk_que.push(Dijk_states(B,dis[B])) ;

    Dijkstra() ;

    states tmp ;

    if(dis[A]==INF){

        printf("No\n") ;

        return ;

    }

    int t=A ;

    while(t!=B){

        tmp.path.push_back(pre_eg[t]) ;

        t=pre[t] ;

    };

    rev(tmp) ; tmp.dev=1 , tmp.ban.push_back(tmp.path[0]) ;

    tmp.t_len=dis[A] ;

    que.push(tmp) ;

    int nums=0 ;

    while(!que.empty()){

        nums ++ ;

        if(nums==K) break ;

        states tp=que.top() ;       

        que.pop() ;

        ext(tp) ; 

    }

    if(nums<K){

        printf("No\n") ;

        return ;

    }

    states tp=que.top() ;

    int len=tp.path.size() ;

    printf("%d-",A) ;

    for(int i=len-1;i>=0;--i){

        printf("%d",from[tp.path[i]]) ;

        if(i!=0) printf("-") ;

    }

    printf("\n") ;

    //printf("%d\n",tp.t_len) ;

}

  

int main()

{

    scanf("%d%d%d%d%d",&n,&m,&K,&A,&B) ;

    for(int i=1;i<=m;++i){

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c) ;

        add_edge(b,a,c) ;

    }

    solve() ;

    return 0 ;

}


评论

热度(1)