1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 人工智能

最短路算法详解

• 人工智能 • 阅读 84

图论基础知识——有向图、无向图

  • 即单向边， i->j有边不一定满足 j->i有边

  • 即双向边， i->j有边一定满足 j->i有边

主要是根据题目要求来建单向边还是双向边

如果是双向边，我们只需要把他拆成 i->j和 j->i的两条单向边就行

无论是单向边还是双向边，对我们最短路都没有什么影响，学会算法以后直接套就行

图论基础知识——建图

  • 开一个 int型的二维数组 tr[i][j]，用来表示 i到 j之间的距离

  • 无脑存图，可以 O(1)判断 i和 j之间是否有边

  • 空间：开一个 tr[n][n]的数组的开销很大，需要根据题目给的空间范围来判断是否可行

  • 时间：对于一个点 i，我们去遍历与它相邻的所有的点的时候，需要 O(n)去枚举每个位置，看 tr[i][j]是否有值，这样n个点就是O ( n 2 ) O(n^2)O (n 2 )，时间开销很大
#define MAX 1050
int tr[MAX][MAX];

for(int i = 1; i  n; ++i){
    for(int j = 1; j  n; ++j){
        if(tr[i][j]){

        }
    }
}
  • 由于我们只想知道与 u相连的点的信息，其他的我们并不在乎，所以链式前向星的本质是用数组模拟了 n个单链表，每个单链表都维护的是起点为 i的边的信息
  • 我们需要开一个 int数组 head， head[i]表示 i点的单链表的头
  • 搞一个结构体记录每条边的信息，假设当前边是 u->v，权值为 c
  • 显然这条边的信息有三个： u v c
  • 由于我们 head[u]的单链表维护的是所有与 u相连的边，所以 head[u]其实就已经记录了 u的信息了
  • 我们搞一个 int型的变量 to，我们令 to = v，即 to记录的是 v的信息
  • 再搞一个 int型的变量 c，记录的是边的权值 c

  • 再搞一个 int型的变量 nex，指向上一条起点为 u的边的 id，用于进行节点的跳转，即维护单链表

  • 数组模拟，常数小

  • 没什么缺点，硬要说有缺点的话，多组输入的时候，有些变量的初始化可能会忘记，比如 tot


int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}


tot = 0;
memset(head, 0, sizeof(head));

for(int u = 1; u  n; ++u){
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
        int c = tr[i].val;

    }
}
  • 跟链式前向星的思想差不多，都是对每个 i都搞一个单链表，维护的是所有起点为 i的边的信息
  • 不过我们可以直接用 vector来维护就行，不需要数组模拟

  • 我们开一个 vector<pair<int,int>>G[MAX]</pair<int,int>，即开一个存 pair类型的 vector数组，对于一条边 (u,v,c),我们只需要往 G[u]里push一个 (v,c)的 pair就行

  • 写起来比链式前向星方便很多

  • vector常数大，可能会被卡


#define m_p(a,b) make_pair(a, b)
typedef pair <int,int> pii;

#define MAX 100050
vector<pii>G[MAX];

for(int i = 1; i  m; ++i){
    cin >> x >> y >> z;
    G[x].push_back(m_p(y, z));

}
for(int u = 1; u  n; ++u){
    for(auto [v, d] : G[u]){

    }
}

单源最短路

A: 即处理起点 s 已知，求从 s出发到其他任意点的最短距离

点的数量： n,边的数量： m
源点、起点： s，终点： t
最短路数组 dis[i]，表示从起点 s到 i点的最短距离
标记数组 vis[i]，不同算法的标记数组的意义不同 (u,v,c)表示 u到 v有一条长度为 c的边

迪杰斯特拉算法

该算法的特点是从 起点开始，采用 贪心算法的策略，采用 加点的的方式，每次遍历到与起始点 距离最近且从 未被访问过的顶点的邻接节点t，将该点t加入集合 B中，直到扩展到终点位置。

从步骤2可以看出，迪杰斯特拉算法的本质是贪心，每一步都是取未确定的点中距离最小的点，然后去更新其他点。这样就可以保证到目前为止，每个点的最短距离一定是由已经确定最短路的点决定的

即我们假设 s到 i的最短路的路径是 s->a->b->c->i，当 i的最短路确定的之前，在 s到 i的路径中的每个点的最短路一定是在这之前就确定的了

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nJbepVrp-1668158087918)(https://cdn.jsdelivr.net/gh/Chelseatr/image@main/uPic/IMG_6485C6692F5B-1.jpeg)]

int n, m, k, x;
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
int dis[MAX];
bool vis[MAX];
void dijkstra(int s){
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for(int i = 1; i  n; ++i){
        int id = -1, minx = inf;
        for(int j = 1; j  n; ++j){
            if(vis[j] == 0 && dis[j] < minx){
                minx = dis[j];
                id = j;
            }
        }
        vis[id] = 1;
        for(int i = head[id]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[id] + tr[i].val){
                dis[v] = dis[id] + tr[i].val;
            }
        }
    }
    for(int i = 1; i  n; ++i)cout << dis[i] << ' ';
}

O ( n 2 ) O(n^2)O (n 2 )

  • 定义方式： pair<p, q>a</p,>, p,q可以是任意类型的变量
  • 比较常用的是： p=q=int，此时 pair等同于:
struct node{
    int x, y;
};
  • 定义方式： pair<int, int>a</int,>
  • 访问方式： a.first和 a.second
  • 产生一个 pair类型的变量的方法是： make_pair(x, y)

普通队列是先进先出，优先队列是优先级高的元素先出队列，并非按照先进先出的要求

什么样的元素的优先级高？这个可以由我们自己决定

默认版本的优先队列是 priority_queue<int></int>，队列的元素是一个 int型的，队顶是最大的元素，俗称 &#x5927;&#x6839;&#x5806;

如果想要最小的元素放在堆顶，则写成 priority_queue<int,vector<int>,greater<int>>q</int></int,vector<int>，俗称小根堆

如果想塞结构体什么的，就得自己重载运算符，这里就不展开了，想知道的可以自己去学一学

如果优先队列塞的是 pair<int, int></int,>，会根据pair的排序方法来确定，pair应该是先第一位，在第二位

简单分析一下，我们的第一层循环是不能优化掉的，因为每次只能确定一个点的最短路，所以要进行n次，但是第二层循环，我们做的是找出一个集合中 dis最小的点，然后去更新与他相邻的所有的点
所以我们其实可以用一个容器去快速地去维护最小的 dis[i]的 i
即我们优先队列需要放两个元素，一个是 dis[i]，另一个是 i，我们取 dis[i]最小的那个，所以想要的是小根堆
用 pair的小根堆，定义方式如下：

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;

q.top()就是堆顶的元素，是 pair类型，是 (dis[i], i)
其实也可以用大根堆 priority_queue<pair<int, int> >q</pair<int,> ，由于pair第一维度最小，所以我们只需要塞 (-dis[i], i)
结构体作为优先队列的元素也是可以的

#define m_p(a,b) make_pair(a, b)
typedef pair <int,int> pii;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}
int dis[MAX];
bool vis[MAX];
void dijkstra(int s){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, 0x3f);
    q.push(m_p(0, s));
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                q.push(m_p(dis[v], v));
            }
        }
    }
}

迪杰斯特拉的贪心算法真的正确吗？

给个例子：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v258EHhD-1668158087919)(https://cdn.jsdelivr.net/gh/Chelseatr/image@main/uPic/image-20221111091902915.png)]

迪杰斯特拉的贪心策略是，每次都找一个距源点最近的点，然后将该距离定为这个点到源点的最短路径；但如果存在负权边，那么直接得到的最短路不一定是最短路径，因为可能先通过并不是距源点最近的一个次优点，再通过一个负权边，使得路径之和更小，这样就出现了错误。

  • 只能处理正权边
  • 朴素版时间复杂度：O ( n 2 ) O(n^2)O (n 2 ), 优先队列优化后时间复杂度:O ( m l o g m ) O(mlogm)O (m l o g m )

Bellman-Ford 算法

Bellman-Ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。

迭代n次，每次都遍历所有边 (u, v, c),去更新 dis[v] = min(dis[v], dis[u] + c)

其原理为连续进行松弛，在每次松弛时把每条边都更新一下，最多进行 n-1次松弛操作

为什么是 n-1?

因为一共 n个点，从起点到终点的简单路径中最多有 n-1条边

所以如果在 n-1 次松弛后还能更新，则说明图中有负环。

  • 极其暴力，复杂度: O(nm)

SPFA

对Bellman-Ford 算法的优化

每次迭代的时候不是所有边都能进行有效的更新

只有当 dis[v]>dis[u]+c的时候才有更新的必要

也就是只有 dis[u]变小了， (u, v, c)的边才有意思

所以我们可以搞一个队列存下来所有 dis变小的节点 u

只要我们队列不为空，即还存在变小的 dis[u]没去更新，我们就需要去更新

更新的时候，如果 dis[v] > dis[u]+c,则说明 dis[v]变小了，我们就放进队列里面，但是如果有些点已经在队列里面了，我们就不需要把他放进去，所以搞一个 vis[i]数组进行标记，如果在队列里就赋1，否则是0

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

bool vis[MAX];
int dis[MAX];
void SPFA(){
    queue<int>q;
    mem(dis, inf);
    q.push(1);dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

不过SPFA很容易被网格图卡成 O(n*m)，有很多玄学优化的方式，但是出题人要是想卡，每种方式都能卡掉

多源最短路-Floyed

多源最短路问题一般是求任意两点间的最短路径

在学会单源最短路的情况下，我们其实可以跑 n次单源最短路求出多源最短路，复杂度是 O(nmlogm)

在 n很小， m很大的情况下，就不适合了

我们可以用 Floyed算法来求解

Floyed本质是动态规划

我们用 dis[k][i][j]表示 i到 j经过若干个编号不超过 k的节点的最短路径的长度

那要求 dis[k][i][j]这个状态的答案，我们可以考虑将其分成两个子状态：

  • i到 j的最短路中不包含 k点，则 dis[k][i][j] = dis[k-1][i][j]
  • i到 j的最短路中包含 k点，则 dis[k][i][j] = dis[k-1][i][k] + dis[k-1][k][j]

则状态转移方程式是：

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])

时间复杂度 O ( n 3 ) O(n^3)O (n 3 )

空间复杂度也是 O ( n 3 ) O(n^3)O (n 3 )

可以发现计算第 k层的时候只用到了第 k-1层，所以可以省略掉这一维度，直接写成 dp[k][i][j] = min(dp[i][j], dp[i][k]+dp[k][j]),减少空间的浪费

由于是dp问题，我们必须解决初始化的问题：如果 i->j存在长度为 c的边，则 dp[i][j] = c,其他的我们就赋个1e9，表示没有边

for(int k = 1; k  n; ++k){
        for(int i = 1; i  n; ++i){
            for(int j = 1; j  n; ++j){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

Original: https://blog.csdn.net/weixin_51216553/article/details/127809802
Author: Chels.
Title: 最短路算法详解

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/656230/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球