前言

那是一条神奇的天路

这几天饱受最短路的摧残洗礼,自愿一篇博客纪念一下。


正文

首先是三种基本的最短路算法。

1.Floyd

最暴力的一种算法($O(n^3)$),也是能处理情形最多的算法(所有).

对于每一对能够通行的点$(u,v)$,任何一个点$k$都应该满足$dst[u][v]<=dst[u][k]+dst[k][v]$,只需要三重暴力枚举使其满足这个条件就好了。

2.dijkstra

3.SPFA


4.次短路

基于$dij+heap$来实现。

普通的最短路是不断更新点与起点之间最短路的值$dst[]$,求次短路只需要添加求次短路的部分。

引进一个数组$dst2[]$存放次短路的值,并且在每次更新的时候进行如下判断:

1.如果最短路能够更新,那么把次短路的值更新为之前的最短并且更新最短路。

2.如果最短路不能更新但是次短路能更新,那么更新次短路。

3.如果次短路能更新,那么更新次短路。

一旦满足任何一个条件,这个点就要加入优先队列,等待下一次操作。

[例题[USACO06NOV]路障Roadblocks](https://www.luogu.com.cn/problem/P2865)

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int id,dst;
    bool operator < (const node &b)const
    {
        return dst>b.dst;
    }
};
struct edge{int to,w;};
priority_queue<node>q;
vector<edge>g[5010];
int dst[5010],dst2[5010];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back((edge){v,w});
        g[v].push_back((edge){u,w});
    }
    
    memset(dst,0x3f,sizeof(dst));
    memset(dst2,0x3f,sizeof(dst2));
    
    dst[1]=0;
    q.push((node){1,0});
    
    while(!q.empty())
    {
        int u=q.top().id,w=q.top().dst;
        q.pop();
        
        if(w>dst2[u])continue;
        
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i].to,w=g[u][i].w;
            bool flag=0;
            
            if(dst[v]>dst[u]+w)//最短路更新,次短路更新为前最短路 
                dst2[v]=dst[v],
                dst[v]=dst[u]+w,
                flag=1;
                
            if(dst[v]<dst[u]+w&&dst2[v]>dst[u]+w)///最短路不更新,次短路更新 
                dst2[v]=dst[u]+w,
                flag=1;
                
            if(dst2[v]>dst2[u]+w)//次短路更新 
                dst2[v]=dst2[u]+w,
                flag=1;
                
            if(flag)q.push((node){v,dst[v]});//有更新就进行拓展操作 
        }
    }
    
    printf("%d",dst2[n]);
    
    return 0;
}

5.$k$短路算法

引入$A*$启发式搜索。

常用的$bfs,dfs$是盲目的搜索,不会去提前判断拓展是否可行,是否更优,而是一味的进行遍历,所以花费的时间比较多(暴搜骗分美汁汁)

而$A*$则不同。

它使用估价函数,提前预判了以后是否会更优,减少了很多无谓的遍历。示意图:

它在dij中的体现为,普通的dij选择的最优,是以已经确定的权值作为关键字,而$A*$优化下的dij,则是把当前确定的权值加上估价函数所计算出的未来权值加在一起,作为关键字。

[[例题]牛慢跑](https://www.luogu.com.cn/problem/P2901)

首先反向存图,一遍dij跑出最短路。

然后用正向存图进行$A*$估价,这一步操作与dij类似,但是不更新值,只是计算出估价值。

只要目标点出堆$k$次,输出当前的权值就好了。

#include<bits/stdc++.h>
using namespace std;
int dst[200005];
int pre1[200005],pre2[200005];
bool f[200005];
int n,m,cnt,ans,sum,k;
struct _edge
{
    int to;
    int w;
    int next;
}edge1[200005],edge2[200005];
struct node1
{
    int v,w;
    bool operator <(const node1 &x)const{return w>x.w;}
};

struct node2
{
    int v,w;
    bool operator <(const node2 &x)const{return w+dst[v]>x.w+dst[x.v];}
};
void add1(int u,int v,int w)
{
    edge1[++cnt].w=w;
    edge1[cnt].to=v;
    edge1[cnt].next=pre1[u];
    pre1[u]=cnt;
}
void add2(int u,int v,int w)
{
    edge2[cnt].w=w;
    edge2[cnt].to=v;
    edge2[cnt].next=pre2[u];
    pre2[u]=cnt;
}
void dij()
{
    priority_queue<node1> q;
    q.push((node1){1,0});
    while(!q.empty())
    {
        node1 x=q.top();
        q.pop();
        if(f[x.v])continue;
        f[x.v]=true;
        for(int i=pre2[x.v];i;i=edge2[i].next)
            if(dst[edge2[i].to]>dst[x.v]+edge2[i].w)
            {
                dst[edge2[i].to]=dst[x.v]+edge2[i].w;
                q.push((node1){edge2[i].to,dst[edge2[i].to]});
            }
    }
}
void A_star()
{
    priority_queue<node2> q;
    q.push((node2){n,0});
    while(!q.empty())
    {
        node2 x=q.top();
        q.pop();
        if(x.v==1)
        {
            sum++;
            printf("%d\n",x.w);
            if(sum>=k)return ;
        }
        for(int i=pre1[x.v];i;i=edge1[i].next)
            q.push((node2){edge1[i].to,x.w+edge1[i].w});
    }
}
int main()
{
    memset(dst,0x3f,sizeof(dst));
    scanf("%d%d%d",&n,&m,&k);
    dst[n]=0;
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add1(x,y,z);
        add2(y,x,z);
    }
    dij();
    A_star();
    for(int i=sum+1;i<=k;i++)
        puts("-1");
    return 0;
}

最后修改:2020 年 04 月 23 日 08 : 23 AM