数据结构与算法学习笔记----Dijkstra

标签：dist int 路径 st ---- Dijkstra 数据结构节点号点

数据结构与算法学习笔记----Dijkstra

@@ author: 明月清了个风
@@ first publish time: 2024.12.17

ps⭐️两个版本的都是模版题，算法讲解直接放在每一题里了，思路中还有对于稀疏图和稠密图的介绍，注意优化版的dijkstra中有几点注意点是和朴素版不一样的。

Acwing 849. Dijkstra求最短路 I

[原题链接](849. Dijkstra求最短路 I - AcWing题库)

给定一个 n n n个点 m m m条边的有向图，图中可能存在重边和自环。

请你求出 1 1 1号点到 n n n号点的最短距离，如果无法从 1 1 1号点走到 n n n号点，则输出 − 1 -1 −1。

输入格式

第一行包含两个整数 n n n和 m m m。

接下来 m m m行，每行包含三个整数 x x x、 y y y、 z z z，表示存在一条从点 x x x到点 y y y的有向边，边长为 z z z。

输出格式

输出一个整数，表示 1 1 1号点到 n n n号点的最短距离。

如果路径不存在输出 − 1 -1 −1。

数据范围

1 ≤ n ≤ 500 1 \leq n \leq 500 1≤n≤500

1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1≤m≤105

图中涉及边长均不超过10000。

思路

Dijkstra是一种经典的图论算法，用于求从一个节点到图中其他所有节点的最短路径。它的基本思想是贪心策略：每次选择当前距离起点最近的节点，然后更新与之相邻节点的距离，直到所有节点的最短路径都被找出来。

算法的步骤如下：

初始化
- 选择一个起点st，初始化起点距离为 0 0 0，其他点距离都是无穷大。
- 创建一个集合 S S S存储所有已经找到最短路的节点，在下面的代码中是bool st[]，用于记录每个点是否已经找到最短路径。
- 创建一个距离数组dist[]记录从源点到所有点的距离。
  
  其实还可以用一个数组或者指针存储前驱点，记录每个点的最短路径是如何到达的。
迭代过程
- 每一轮迭代中，从尚未确定最短路的点中找到dist最近的点，即当前的最短路径节点，记为t。
- 将t加入集合 S S S
- 更新t所能到达的所有点v的距离dist[v]，检查通过t到v距离（也就是路径 s t → t → v st \rightarrow t \rightarrow v st→t→v）是否比源点st到v点（也就是路径 s t → v st \rightarrow v st→v）的距离更近dist[v] = min(dist[v], dist[t] + g[t][v])
- 因为每一轮中都能确定一个点的最短距离，因此 n n n轮循环后，算法结束。
图的存储

对于Dijkstra来说，图的存储和遍历也是很重要的，这里需要讲解以下稠密图和稀疏图的分类和对应的存储方式
- 稠密图：边的数量接近其最大可能边数的图，换句话说，稠密图的边数更多，举个例子，对于一个有 n n n个节点的无向图，它的最大边数为 n ( n − 1 ) 2 \frac {n(n - 1)} {2} 2n(n−1)，这是完全图的边数，空间复杂度可以达到 O ( n 2 ) O(n^2) O(n2)每一对节点之间都有一条边，边数越接近这个数量，就可以视为稠密图。通常使用邻接矩阵进行存储
- 稀疏图：边数远远小于最大边数，空间复杂度在 O ( n ) O(n) O(n)或者 O ( n log ⁡ n ) O(n\;\log n) O(nlogn)，通常使用邻接表进行存储。

时间复杂度：对于朴素Dijkstra来说，如果使用邻接矩阵存储图，时间复杂度为 O ( n 2 ) O(n^2) O(n2)，下面的代码可以看出是两重循环。

正确性证明

贪心策略正确性

假设集合 S S S中的所有节点都已经处理完毕，即已确认从源点st到集合 S S S中任意点 i i i的最短距离为 d i s t [ i ] dist[i] dist[i]，那么dijkstra每次选择的是集合外的距离源点最近的点u，并将其加入 S S S中

需要证明：选择点u，不会错过更好的路径。

反证法：假设u不是下一个最短路径节点，那么在源点st到点u的路径上，一定存在一个点v有dist[v] < dist[u]，但是，我们在算法的运行中，选择的是距离源点最近的节点且此节点尚未加入集合 S S S，那么说明肯定不存在点v，因此贪心策略正确。
最短路径正确性

当节点u被加入集合 S S S中时，节点u的dist[u]为从源点到此点的最短路径。因为算法每次选择的都是未处理节点中距离源点最近的节点，因此每次更新其他节点的距离时都会确保使用已确定最短路径的节点去更新邻接节点的距离，保证每个被处理节点的最短路径是准确的。
算法终止条件

当算法完成时，每个节点v的dist[v]为从源点st到此点的最短路径

反证法：假设算法完成时某个节点v的距离不是最短路径距离，并且当前路径是 s t → a → v st \rightarrow a \rightarrow v st→a→v，如果有更短路径的存在，假设这条路径是 s t → b → v st \rightarrow b \rightarrow v st→b→v，那么根据贪心策略正确性和最短路径正确性，在选择节点b更新其邻接节点时，一定会更新此路径 s t → b → v st \rightarrow b \rightarrow v st→b→v的距离，所以路径 s t → a → v st \rightarrow a \rightarrow v st→a→v也一定不会是最短路径。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, inf = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijstra()
{
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    
    for(int i = 1; i <= n; i ++)
    {
        int t = -1; 
        for(int j = 1; j <= n; j ++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        
        st[t] = true;
        
        for(int j = 1; j <= n; j ++)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    
    
    if(dist[n] == inf) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    
    memset(g, 0x3f, sizeof g);
    
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    
    cout << dijstra() << endl;
    
    return 0;
}

Acwing 850. Dijkstra求最短路 II

[原题链接](850. Dijkstra求最短路 II - AcWing题库)

给定一个 n n n个点 m m m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 1 1号点到 n n n号点的最短距离，如果无法从 1 1 1号点走到 n n n号点，则输出 − 1 -1 −1。

输入格式

第一行包含两个整数 n n n和 m m m。

接下来 m m m行，每行包含三个整数 x x x、 y y y、 z z z，表示存在一条从点 x x x到点 y y y的有向边，边长为 z z z。

输出格式

输出一个整数，表示 1 1 1号点到 n n n号点的最短距离。

如果路径不存在输出 − 1 -1 −1。

数据范围

1 ≤ n , m ≤ 1.5 × 1 0 5 1 \leq n, m \leq 1.5 \times 10^5 1≤n,m≤1.5×105

图中涉及边长均不超过10000。

思路

朴素版dijkstra中并未提及时间复杂度，在这里一起进行分析。

根据朴素版的算法流程和代码可以发现，时间复杂度最高的地方就是两重循环找目前集合 S S S之外的具有最短路径的点，因此朴素版的dijkstra时间复杂度为 O ( n 2 ) O(n^2) O(n2)，而针对在一个集合中找最小值，我们已经学过使用小根堆进行查找（链接在这）,可以进行优化使用小根堆维护当前的最短路径，将查找的时间复杂度降低到 O ( 1 ) O(1) O(1)，再用查找的结果更新其他点的距离，时间复杂度是 O ( m log ⁡ n ) O(m \log n) O(mlogn)，因为最多要更新 m m m条边，堆的修改操作时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)。

注意点：

此题中使用的邻接表的存储方式，和上一题的点、边数量进行对比，可以看出这题的边数极少。
堆有两种方式实现，一种是手写堆，这样可以保证堆中只有 n n n个数，另一种是使用stl库中priority_queue，但是其不支持修改元素的操作，因此堆中元素可能会达到 m m m个。这里需要说明的是，对于多出来的边其实并不会额外进行处理，比如在之前有两个点都对点v距离进行了更新的时候，那么堆中都会有两组值(dist1, v), (dist2, v)，我们进行维护的时候会取出较小的一组值更新其邻接点的距离，当处理到第二组值时，和朴素版一样，使用st[v]判断是否已经处理过就行了。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 150010, inf = 0x3f3f3f3f;

typedef pair<int, int> PII;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i= h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
        
    }
    
    if(dist[n] == inf) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

标签：dist,int,路径,st,----,Dijkstra,数据结构,节点,号点
From： https://blog.csdn.net/weixin_60278491/article/details/144537091

数据结构与算法学习笔记----Dijkstra