k短路问题

问题描述:

从一幅有向图的起点走到终点,途中可以经过一个点多次,到达终点后依然可以继续行走,但是不能中途停留。求所有这样的路径中第l短的长度。

Solution1:迭代加深搜索

最容易想到也最自然的做法是将各个从起点到达终点的路径一一枚举,排序后输出第k条路径。但是由于路径条数是无穷的,我们不可能枚举所有路径。解决方法和“埃及分数”问题类似。于是在搜索时加以限制,就可以求出一定长度限制以下的路径。

优化:在搜索时若当前路径长度超过限制长度时,我们需要剪枝,停止继续搜索这个分支。同时,将这个剪枝继续加深,如果当前路径长度加上当前点到终点的距离大于限制长度,剪枝。这种最优性剪枝在实际运用中十分有效。

缺陷:这种搜索在判断是否无解的问题上不是很有效。我们不知道限制长度迭代到多大时应该输出无解。但是这种方法在其他方面还是比较优秀的。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 1001
#define ME 100001
#define MXDIS 100

using namespace std;

int fst[MX],nxt[ME],v[ME],w[ME],lnum;
int fin[MX],nin[ME],vin[ME],win[ME],inum;
int n,m,S,T,K;

void addeg(int nu,int nv,int nw){nxt[++lnum]=fst[nu];fst[nu]=lnum;v[lnum]=nv;w[lnum]=nw;}

void addin(int nu,int nv,int nw){nin[++inum]=fin[nu];fin[nu]=inum;vin[lnum]=nv;win[lnum]=nw;}

void input()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        addeg(a,b,c);
        addin(b,a,c);
    }
    scanf("%d%d%d",&S,&T,&K);
}

int dis[MX],q[MX],inq[MX];
void SPFA(int frm)
{
    int t=1,h=0,nu,nv;
    for(int i=1;i<=n;i++)dis[i]=99999999;
    q[++h]=frm;
    dis[frm]=0;
    inq[frm]=1;
    while(h>=t)
    {
        nu=q[(t++)%MX];
        for(int i=fin[nu];i!=-1;i=nin[i])
        {
            nv=vin[i];
            if(dis[nv]>dis[nu]+win[i])
            {
                dis[nv]=dis[nu]+win[i];
                if(!inq[nv])
                {
                    inq[nv]=1;
                    q[(++h)%MX]=nv;
                }
            }
        }
        inq[nu]=0;
    }
}

int ans,top;

void dfs(int x,int now)
{
    if(x==T&&now!=0)ans++;
    if(ans>=K){cout<<top<<endl;exit(0);}
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        if(dis[v[i]]+now+w[i]>top)continue;
        dfs(v[i],now+w[i]);
    }
}

void work()
{   
    SPFA(T);
    if(dis[S]>100000){cout<<-1<<endl;return;}
    for(int i=dis[S];i<=dis[S]+MXDIS;i++)
    {
        ans=0;
        top=i;
        dfs(S,0);
    }
    cout<<-1<<endl;
}

void init()
{
    memset(fst,0xff,sizeof(fst));
    memset(fin,0xff,sizeof(fin));
    inum=-1;
    lnum=-1;
}

int main()
{
    init();
    input();
    work();
    return 0;
}

Solution2:A*

首先我们需要一定的灵感:次短路和最短路的不同在于某一步的失策。也就是说:你按着最短路向终点走,有一步突然走错了,然后紧接着你按着现在的最短方向走到了终点,那么这条路也许就是次短路。是不是次短路取决于你是哪一步走错了。如果是一步重要的路走错了,这条路也许会变地非常长,反之不会太长。

如何评估这一步走错对最短路的影响?我们使用A*算法的估价函数。用F(x)表示以当前的走法走到x的距离,H(X)表示x到终点的最短路长度。那么对于x节点,我们下一步可以选择“走对”或者“走错”,于是这一个x又可以扩展到相邻的节点。每一次我们选择F(x)+H(X)最小的x节点扩展,那么最先到达终点时终点的F(x)就是最短路(是不是很像dijstra?),第二次到达终点就是次短路。Why?简单地将讲,我们的扩展方式确保了扩展节点的F(x)+H(x)一定是递增的,而到达了终点,H(x)=0,那么F(x)就是递增的。

这种算法在随机数据下,若边权较小,k较大,速度不如上一种方法。但是它的优点是稳定。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define MX 10001
#define ME 100001

using namespace std;

int n,m,k;
int S,T;

struct Node
{
    int p,f,h;
    bool operator <(const Node a)const
    {
        if(a.f+a.h<f+h)return 1;
        else return 0;
    }
    Node(int a,int b,int c)
    {
        this->p=a,this->f=b,this->h=c;
    }
};
Node make(int a,int b,int c)
{
    Node thi(a,b,c);
    return thi;
}

int dis[MX];

class graph
{
    public:
    int fst[MX],nxt[ME],v[ME],w[ME],lnum;
    int q[MX],inq[MX];
    priority_queue<Node> mp;
    void init()
    {
        memset(fst,0xff,sizeof(fst));
        lnum=-1;
    }
    void addeg(int nu,int nv,int nw)
    {
        nxt[++lnum]=fst[nu];
        fst[nu]=lnum;
        v[lnum]=nv;
        w[lnum]=nw;
    }
    void SPFA(int frm)
    {
        int h=0,t=1,x,y;
        memset(dis,0x3f,sizeof(dis));
        q[++h]=frm;
        dis[frm]=0;
        inq[frm]=1;
        while(h>=t)
        {
            x=q[(t++)%ME];
            for(int i=fst[x];i!=-1;i=nxt[i])
            {
                y=v[i];
                if(dis[y]>dis[x]+w[i])
                {
                    dis[y]=dis[x]+w[i];
                    if(!inq[y])
                    {
                        q[(++h)%ME]=y;
                        inq[y]=1;
                    }
                }
            }
            inq[x]=0;
        }
    }
    int Astar(int frm,int to)
    {
        Node x(0,0,0);
        int cnt=0;
        if(frm==to)k++;
        if(dis[frm]>100000)return -1;
        mp.push(make(frm,0,dis[frm]));
        while(!mp.empty())
        {
            x=mp.top(),mp.pop();
            if(x.p==to)
            {
                cnt++;
                if(cnt==k)return x.f+x.h;
            }
            for(int i=fst[x.p];i!=-1;i=nxt[i])mp.push(make(v[i],x.f+w[i],dis[v[i]]));
        }
        return -1;
    }

}g1,g2;

void input()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        g1.addeg(a,b,c);
        g2.addeg(b,a,c);
    }
    scanf("%d%d%d",&S,&T,&k);
}

int main()
{
    g1.init(),g2.init();
    input();
    g2.SPFA(T);
    printf("%d\n",g1.Astar(S,T));
    return 0;
}

比较

刚才我们讨论了两种解决k短路问题的办法,也得出了两种较简单的算法。

但是可以说,第一种算法是不完备的。首先,在讨论中我们发现它无法判断是否有解。其次,如果边权值差异较大,图又是稀疏图,将会浪费很长时间枚举路径长度。因此这种方法在很大程度上依赖于数据的特性。

所以推荐第二种做法

拓展

k短路问题还有很多变种,比如不能经过相同节点k短路,(可以用第一种方法在一定特征的数据内解决),以及k很大的k短路。这些问题可以用特殊的数据结构来帮助解决,但主要思想还是依赖F(X)和H(X)函数的值。

推荐一个文章:可持久化堆和k短路-俞鼎力

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *