算法 A*算法

y总说的已经很详细啦~~我需要注意的地方。

• A*算法要有一个启发函数来引领着我们去搜索, 一般用在搜索空间很大的题目，比如最小步数模型里面。
• A*算法可以运用在没有负环的边的里面。
• $基本流程：优先队列存储两个值， 第一个值f = g + h, g为该点到起点的真实距离， h 为该点到终点的估计距离，第二个值一般是该点的状态（如果是最短路就是该点，如果是最小步数模型就是该字符串），然后 不断迭代更新，当终点第一次出来的时候就为最小。$
• 正确性的保证，估计距离必须要小于真实距离， 如果存在误解情况还不不如BFS，因为BFS操作都是O(1)的， A*操作是O(log)的。所以要特殊处理无解情况。
• A*只能保证终点出队的时候是最小值，它他点不一定能保证为最小值，终点出队几次就为第几小，可以应用在第K短路问题中。
• BFS, dijkstra, A对比与联系
  dijkstra可以看成是估计距离全部为0的A算法
  BFS是在入队的时候判断重复
  dijkstra在出队的时候判断重复
  A*算法不判断重复，只判断终点是否出队即可。

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <cstring>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 1010, M = 2e5 + 10;

int h[N], rh[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int n, m, s, T, k;

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

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    heap.push({0, T});
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int av = t.y, distance = t.x;
        if(st[av])continue;
        st[av] = true;
        for(int i = rh[av]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int Astart()
{
    dijkstra();
    priority_queue<PIII, vector<PIII>, greater<PIII> > heap;
    heap.push({dist[s], {0, s}});
    int cnt = 0;
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int av = t.y.y, d = t.y.x;
        if(av == T)cnt ++;
        if(cnt == k)return d;

        for(int i = h[av]; ~i; i = ne[i])
        {
            int j = e[i];
            heap.push({dist[j] + d + w[i], {d + w[i], j}});
        }
    }
    return  -1;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(h, a, b, c);
        add(rh, b, a, c);
    }
    cin >> s >> T >> k;
    if(s == T)k ++;
    cout << Astart() << endl;
    return 0;
}