这篇文章的前两个 Solution 是我一年多前写的，第三个 Solution 当时不会，因此拖到 19 年才写出来。

k 短路问题

问题描述：

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

Solution1: 迭代加深搜索

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

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

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

时间复杂度：$O(???)​$

#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 较大，速度不如上一种方法。但是它的优点是稳定。

时间复杂度 $O(NK\log K)$

一种卡 A* 的图：构造一个大环，包含起始节点和终止节点即可。

#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;
}

Solution3: 可并堆

可并堆的做法是对 A* 做法的一种改进。

由于 A* 做法可能在多次扩展后才能找到一条路径，造成了其时间的浪费，也使得时间复杂度变得非常大。

如果可以在每次扩展时都能得到一条路径，就可以将时间优化到 $O(K\log N)$这个级别。

怎么做到这样呢？我们先将反图的最短路树建立出来。任何一条 $S-T$路径都可以表示为若干树边和非树边交替出现的序列。我们可以直接使用其非树边序列表示这个序列。

现在定义几个东西：

• $dis(x)$：$x$点沿着最短路树走到 $T$的路径长度。
• $e.s,e.t,e.w$：非树边 $e$的起始节点，终止节点和长度。
• $\Delta e$：从 $e.s$出发走非树边 $e$，再走最短路，比直接走 $e.s$的最短路多走的距离。即 $\Delta e=dis(e.t)+e.w-dis(e.s)$

一条路径的长度，可以表示为每条非树边多走的距离之和。即 $\sum \Delta e$

如果我们找到了一条合法的路径 $e_1,e_2,\cdots ,e_m​$，我们能否像 A* 算法一样找到一个比这条路径略长的新的路径呢？而且需要保证每次找到的路径不重复。

这个好办，有两种方式可以找到一条新的合法路径，并且这条路径尽可能的短，而且可以保证不重复。

• 将 $e_m$替换为一条 $\Delta$更大的可行非树边，即 $e_1,e_2\cdots ,e_m’$
• 将序列后面添加上一条 $\Delta$最小的可行非树边，即 $e_1,e_2\cdots ,e_m,e_{m+1}$

正确性？我们将非树边序列映射到一张新的图上。将 $e_i$映射为新图的点，如果 $\cdots e_i,e_j\cdots $是一个合法的路径 (即 $e_i.t$可以通过树边走到 $e_j.s$)，那么 $e_i$和 $e_j$之间存在一条边。我们现在即在求这张新的图的不规定终点的 $k​$短路。于是，算法的正确性就非常显然了。

对于所有的非树边序列，我们只需要保存它的 $\sum \Delta e$以及 $e_m$即可。每次，我们从所有的已知的非树边序列中选择 $\sum \Delta e​$最小的那一个作为新的路径，并且从它开始进行扩展，将扩展出的新序列加入已知序列的集合中。已知序列的集合需要用堆 (优先队列) 维护。

接下来就是如何扩展的问题了。先考虑如何找到一条边的所有可行后继非树边。这些边就是所有挂在最短路树上 $e_m.t\cdots T$上的非树边。也就是说一条边的可行后继非树边集合为 $e.t$在最短路树上的父亲的集合并上挂在 $e.t$上的非树边。由于我们在扩展时寻找的是最小可行非树边，因此将这个集合用可并堆维护，每个点的集合由其父亲的集合继承而来。这样，一条非树边的最小可行后继非树边就是 $e.t$的可并堆的跟。

如何替换一条边呢？一条边所在的可并堆的两个儿子可以替换这条边。

综上，就是 $O(K\log N)$的 $K$短路做法。

需要注意几个地方：

• 1. 当所有的路径找完了，需要及时退出，以免 $pop​$一个空的优先队列。
• 2. 当图中根本就没有第二条路径，$S​$的可并堆将是空的，这时候需要直接退出。

下面是魔法猪学院的代码。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#define MX 200008
#define oo 123123123123123

using namespace std;

template <typename T> void read(T& x)
{
    x = 0; char c = getchar(); bool f = 0;
    while(!isdigit(c) && c!='-') c = getchar();
    if(c == '-') f = 1, c = getchar();
    while(isdigit(c)) x = x*10+c-'0', c = getchar();
    if(f) x = -x;
}

int N, M;
double E;

struct PNODE
{
    int p;
    double d;

    PNODE (const int& p0 = 0, const double& d0 = 0) : p(p0), d(d0) {}
    bool operator < (const PNODE& t) const {return d > t.d;}
};

struct SNODE
{
    int ls, rs, ed, len;
    double w;

    SNODE (const int& e0 = 0, const double& w0 = 0) : ls(0), rs(0), ed(e0), len(0), w(w0) {}
};

struct HEAP
{
    int cnt;
    SNODE tre[MX*6];

    int merge(int x, int y)
    {
        int a;
        if(!x || !y) return (x|y);
        if(tre[x].w < tre[y].w) swap(x, y);
        tre[a = ++cnt] = tre[y];
        tre[a].ls = merge(x, tre[y].ls);
        if(tre[tre[a].ls].len > tre[tre[a].rs].len) swap(tre[a].ls, tre[a].rs);
        tre[a].len = tre[tre[a].ls].len + 1;
        return a;
    }
};

struct GRAPH
{
    int fst[MX], nxt[MX], v[MX], lnum;
    int que[MX], inq[MX], pre[MX];
    double w[MX], dis[MX];

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

    void spfa(int frm)
    {
        int h = 1, t = 1, x, y;
        for(int i=1; i<=N; i++) dis[i] = +oo;
        que[h] = frm;
        dis[frm] = 0;
        inq[frm] = 1;
        while(h >= t)
        {
            x = que[(t++)%MX];
            inq[x] = 0;
            for(int i=fst[x]; i; i=nxt[i])
            {
                y = v[i];
                if(dis[y] > dis[x] + w[i])
                {
                    dis[y] = dis[x] + w[i];
                    pre[y] = i;
                    if(!inq[y])
                    {
                        que[(++h)%MX] = y;
                        inq[y] = 1;
                    }
                }
            }
        }
    }
};

HEAP H;
GRAPH G, R;
priority_queue<PNODE> Q;

void input()
{
    int a, b; double c;
    read(N); read(M); scanf("%lf", &E);
    for(int i=1; i<=M; i++)
    {
        read(a); read(b); scanf("%lf", &c);
        G.addeg(a, b, c);
        R.addeg(b, a, c);
    }
}

PNODE seq[MX];
int rot[MX];

void work()
{
    R.spfa(N);
    for(int i=1; i<=N; i++) seq[i] = PNODE(i, R.dis[i]);
    sort(seq+1, seq+N+1);
    for(int a=N; a>=1; a--)
    {
        int x = seq[a].p;
        for(int i=G.fst[x]; i; i=G.nxt[i])
        {
            if(i != R.pre[x])
            {
                H.cnt++;
                H.tre[H.cnt] = SNODE(G.v[i], R.dis[G.v[i]]-R.dis[R.v[i]]+G.w[i]);
                rot[x] = H.merge(rot[x], H.cnt);
            }
        }
        rot[x] = H.merge(rot[x], rot[G.v[R.pre[x]]]);
    }
    if(rot[1]) Q.push(PNODE(rot[1], H.tre[rot[1]].w));
    int cnt = 0;
    if(E-R.dis[1] >= 0) E -= R.dis[1], cnt++;
    while(E > 0)
    {
        if(Q.empty()) break;
        PNODE e = Q.top();
        Q.pop();
        if(E-(e.d+R.dis[1]) < 0) break;
        else E -= (e.d+R.dis[1]), cnt++;
        if(H.tre[e.p].ls) Q.push(PNODE(H.tre[e.p].ls, e.d - H.tre[e.p].w + H.tre[H.tre[e.p].ls].w));
        if(H.tre[e.p].rs) Q.push(PNODE(H.tre[e.p].rs, e.d - H.tre[e.p].w + H.tre[H.tre[e.p].rs].w));
        if(rot[H.tre[e.p].ed]) Q.push(PNODE(rot[H.tre[e.p].ed], e.d + H.tre[rot[H.tre[e.p].ed]].w));
    }
    printf("%d\n", cnt);
}

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

比较

刚才我们讨论了三种解决 k 短路问题的办法，也得出了两种较简单的算法，一种高效的算法

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

所以推荐第二种做法。

如果你对自己的代码能力有信心，你可以尝试在考场上实现第三种做法。由于第三种做法各个变量的定义较为复杂，一般需要先在草稿纸或者脑子里重新推算一遍，才能保证在实现的时候不出问题。实际上，这种做法出现 bug 的概率不大，如果过了样例，AC 应该是十拿九稳的事情。但是也需要注意上文提到的那几个需要特殊注意的地方。

拓展

k 短路问题还有很多变种，比如不能经过相同节点 k 短路，(可以用第一种方法在一定特征的数据内解决，也可以用 bitset 等记录经过的节点，运用第 2,3 种做法)。

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