最短路

algorith · 2022-11-19 08:41:41 · 个人记录

定义

在一个图中，从起点到终点路径选择方案中，所有路径 权值之和最小的路径选择方案。

他们的特点如下

dfs枚举

这是最没思路，和时间复杂度最高的，也就是暴力。

其思路就是枚举所有可能，最后找最小值

void dfs(int i,int now){
    if(i==end){
        ans=min(ans,now);
        return;
    }
    for(int j=1;j<=n;++j)
    if(!vis[j]&&g[i][j]){
        vis[j]=1;
        dfs(j,now+g[i][j]);
        vis[j]=0;
    }
}

Dijkstra

Dijkstra主要采用贪心策略，当所有边权都是非负数 时，从起点(此处记做 s )出发，把 i 到起点的最 短路路径的长度记为dis_i，dis_s初始为0，在 未标记(初始)点中寻找距离起始点路径最短的顶点，并 将其标记(即确定了起点到它的最短路，因为此时是距离 起点最近，所有没有其他到这个点更近的路径，所有即 确定了它)，直到所有顶点都被标记为止。

时间复杂度O(n^2)

实现

首先初始化

memset(vis,0,sizeof vis)//标记数组，初始全没被标记
memset(dis,0x3f,sizeof dis)//最短路记录，初始化为无穷大
dis[s]=0;//起点到自己的距离为0

主体

for(int i=1;i<=n;++i){
        int mi=0x7fffffff,k;
        for(int j=1;j<=n;++j){
            if(!vis[j]&&dis[j]<mi){  //寻找此时没被标记离起点最近的点
                mi=a[1][j];
                k=j;
            }
        } 
        vis[k]=1;  //标记他
        for(int j=1;j<=n;++j){
            if(!vis[j]&&a[j][k]&&dis[j]>a[j][k]+dis[k]) //更新出与其相邻的未被标记的点的此时的最短路长度
            dis[j]=a[j][k]+dis[k];
        }
    }

堆优化Dijkstra

在朴素Dijkstra中，每次寻找距离起点最近的点的时间 复杂度为O(n)，寻找一个集合的最小值我们可以想到 数据结构 "堆"(或优先队列)，它可以用O(log_n)的 时间复杂度寻找出一个集合最小值，此处我们可以用上 它，来找每次距离起点最近的点。

同时该程序用了链式前向星优化了，每个点直接记录下 了它相邻的点直接用，而不是遍历n个点，再在过程中 判断相不相邻。

时间复杂度O(mlogn)

struct node{
    int t,z;
};
int n,m,dis[505],vis[505];
vector <node> q[505];  //用vector来链式前向星
void dij(){
    memset(dis,0x3f,sizeof dis);
    priority_queue<pair<int,int> > v; //大根堆
    v.push({0,1});  //路径长度，点编号，用pair的话，堆会直接把第一个数(first)当做关键字
    dis[1]=0;
    while(!v.empty()){   //只要堆不为空
        int cur=v.top().second;   //找出最近的点编号
        v.pop();
        if(vis[cur])continue;
        for(int i=0;i<q[cur].size();++i){
            int to=q[cur][i].t;
            if(dis[to]>dis[cur]+q[cur][i].z){
                dis[to]=dis[cur]+q[cur][i].z;
                v.push({-dis[to],to});   //大根堆存其负数相当于小根堆
            }
        }
    }
}

例题P4779 【模板】单源最短路径（标准版）

为什么普通Dijkstra不能处理有负权的图

这就因为其贪心策略，默认是后面加会越来越大，而不 会变小，所以点会直接确定

比如上面这个图，如果按 Dijkstra的策略来的话

其核心代码只有4行

//单向边
for(int k=1;k<n;++k)  //只可能更新n-1次
    for(int i=1;i<=m;++i)  //m条边
        if(dis[v[i]]>dis[u[i]]+w[i])
            dis[v[i]]=dis[u[i]]+w[i];

SPFA

其是Bellman-Ford的一个优化过来的算法，我们可以发 现Bellman-Ford中，每次都要拿每个点去更新与其相邻 的点，而实际上，如果几次循环，一个点的值一直没 变，那么它更新其他点也只会更新一次，之后是更新不 了的。于是我们就可以只把值有改变的点用来更新。于 是我们用一个队列来存这些需要改变的点，如果一个点 的值有改变，且队列里没有它(此处是一个小优化，因为 队列存的是编号，而用来改变的值是一样的所以，没必 要该两次)就将其入队。当用它更新完其他点后，就让它 出队。

时间复杂度O(km),k：用点次数，一般时间复杂度

while(!q.empty()){
    for(int i=head[q.front()];i;i=edges[i].next){
        if(ans[q.front()]+edges[i].z<ans[edges[i].to]){
            ans[edges[i].to]=ans[q.front()]+edges[i].z;
         if(!inq[edges[i].to])
            q.push(edges[i].to),inq[edges[i].to]=1;
        }
    }
   inq[q.front()]=0;
    q.pop();
}

判负环

即几个负边权组成的环，一直转下去会让答案无限小， 无解

例题P3385 【模板】负环

首先我们要知道，对于一个不存在负环的图，从起点到 任意一个点最短距离经过的点最多只有 n 个，所以一 个点它最多只会被更新n次，当一个点更新次数超过

优点：代码好写，思路简单易理解

if(dis[i][j]<dis[i][k]+dis[k][j])  //松弛操作
    dis[i][j]=dis[i][k]+dis[k][j];

核心代码如下

for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];

最开始只允许经过1号顶点进行松弛，接下来只允许经过 1和2号顶点进行松弛…允许经过1…n号所有顶点进 行中转，求任意两点之间的最短路程。用一句话概括就 是：从i号顶点到j号顶点只经过前k号点的最短 路程

例题：B3647 【模板】Floyd 算法

但其时间复杂度不如堆优化dij O(n^2logn),有时不 如spfa O(knm)

其它

建反边

有时题目会给出一个有向图，问其它所有点到其中某一个点的最短路长度总和。 常规思路的话可能就是跑n遍dij或spfa或floyd，可其时间复杂度达到了