算法提高课汇总

算法思路

求第$k$短路, 在计算过程中需要将顶点$u$与其所有后续顶点构成的边全部考虑. 对考虑较多的状态
可以用$A^*$ 算法优化时间.

$A^*$

估价函数

对于顶点$u$, 其到终点距离的估价函数需要 $\le$ 其到终点的最小距离, 且越接近越好. 本题可以通过
求从终点出发的反向图的单源最短路, 使得$f(u) = g(u)$.

求$k$短

根据算法优先队列的性质, 第一次终点出队的路径距离一定是最短路. 若继续算法, 那么下一次终点出队
的路径一定是不考虑最短路的最短, 也就是次短路. 所以终点第$k$次出队的距离即所求的第$k$短路.

具体实现

注意:

1. 注意需要考虑无解情况: 因为题目允许可以重复路径, 所以只要存在一条最短路, 就可以通过重复得到
   第$k$短. 所以无解只发生在从起点到终点不存在路径时.

2. 题目要求至少存在一条边, 而当起点与终点重合时, 最短路一定是不走. 所以此时需要将$k + 1$, 额外
   考虑此种情况.

实现代码

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;

const int N = 1010, M = 2e4 + 10, INF = 0x3f3f3f3f;

int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N]; bool st[N]; //dikjstra

void add(int h[], int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++ ;
}

void dijkstra()
{//以T作为起点求单源最短路 得到估价函数
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.push({0, T});

    while( heap.size() )
    {
        int u = heap.top().y;
        heap.pop();

        if( st[u] ) continue;
        st[u] = true;

        for ( int i = rh[u]; ~i; i = ne[i] )
        {
            int v = e[i];
            if( dist[v] > dist[u] + w[i] )
            {
                dist[v] = dist[u] + w[i];
                heap.push({dist[v], v});
            }
        }
    }
}

int astar()
{
    //<启发函数, <起点到u的距离, 顶点>>
    priority_queue<piii, vector<piii>, greater<piii>> heap;
    heap.push({dist[S], {0, S}});

    int cnt = 0; //记录终点出队次数
    while (heap.size())
    {
        int u = heap.top().y.y, distance  = heap.top().y.x;
        heap.pop();

        if ( u == T && ++cnt == K ) return distance;

        for ( int i = h[u]; ~i; i = ne[i] )
        {
            int v = e[i];
            heap.push({distance + w[i] + dist[v], {distance + w[i], v}});
        }
    }
    return -1; //不存在第k条边 
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    while ( m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h, a, b, c);
        add(rh, b, a, c);
    }
    scanf("%d%d%d", &S, &T, &K);
    if ( S == T )   K ++;

    dijkstra();
    if( dist[S] == INF )    puts("-1"); //不存在最短路
    else    printf("%d\n", astar());   //若输出-1 表示不存在第k短路

    return 0;
}