单源最短路之--SPFA A*

　　只是谈谈我今日所学，啊，昨日舍友打游戏弄得我睡不好，今天学的迷迷糊糊，若有不当之处望指正。

• SPFA:

　　单源最短路径的非常高效的方法，且可以处理带有负权的边。

　　@para dis[] 用来记录到目标点的预估值：初始时为Inf（无穷大），只有dis[target] = 0;

　　用队列来保存优化的节点，（bool）in_que[]来记录某个点是否在队列中，每次入队出队都要记得记录状态。

　　　　优化时每次先取得que首节点cur，枚举与cur相连的节点，用cur当前的最短的路径的估计值与下一个相连节点的估计值加上这两节点的间距，进行松弛操作，若松弛成功则当前的节点的改变还会影响与之有联系的其他节点，所以要将执行了松弛操作的节点入队（当然已经入队就不用管了，所以需要in_que[]数组来标记每个点的在队状态）。如此一直操作，直至队列为空，则所有点到单源最短路已经确定。若可能存在负权，则要另加判断每个点的入队次数，入队的次数超过n，则存在负环。

 

/*现只考虑只有正权*/
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define Inf 0x3f3f3f3f
const int maxe = 1e4, maxp = 1e3;
struct Edge{
    int to, w;
    int next;
}edge[maxe];
int head[maxp], cnt; //head[]是点集，存的是边的最大编号，再次强调
int dis[maxp]; //其他所有点到单源点的距离
bool in_que[maxp];
int st, en;

void ini()
{
    memset(dis, sizeof(dis), Inf);
    dis[st] = 0;
}
void add_edge(int from, int to, int w)
{
    cnt += 1;
    edge[cnt].to = to;
    edge[cnt].w = w;
    edge[cnt].next = head[from];
    head[from] = cnt;
    return;
}
int spfa()
{
    queue<int> que; while(que.size())   que.pop();
    que.push(st);
    in_que[st] = true;

    while(que.size()){
        int cur = que.front();
        que.pop();
        in_que[cur] = false;
        for(int i = head[cur]; i; i = edge[i].next){//所有与cur相连的点遍历，松弛更新
            if(dis[edge[i].to] > dis[cur] + edge[i].w)
            {
                dis[cur] = dis[edge[i].to] + edge[i].w;
                if(!in_que[edge[i].to]){
                    que.push(edge[i].to);
                    in_que[edge[i].to] = true;
                }
            }
        }
    }
}

 

• A*：启发式搜索（看别人是这么叫的~）

　　代价方程： f = g + h. 　　1）f：代价。2）g：当前实际已经消耗的代价。3）h：预估的代价（我目前碰到的是先预处理反向建图得到预估代价）

　　priority_queue：利用priority_queue来存储节点，重载比较函数，将f（代价最小的作为优先级最高的），注意priority_queue是大顶堆，所以重载时要弄清返回true时的变量顺序。具体使用时和bfs一样，可以说是更加优化的bfs。这里就不再贴代码，仿照bfs即可。