朴素Dijkstra算法

蔚落 2022-11-05 08:32 106阅读 0赞

**上一篇博客：[通俗易懂的字符串哈希算法，你确定不来看一下吗?][Link 1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  简介
 *  图的存储
 *  算法思路
 *  算法实现
 *  例题
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  数据范围
         *  输入样例
         *  输出样例
     *  题解
     *   *  解题代码

# 简介 #

`Dijkstra算法` 用来求 所有边权都是正数 的 **单源最短路**。**边权** 即两个点之间的距离；**单源** 即只求从源点（起点，终点也称为汇点）到其他点的最短距离；

朴素Dijkstra 算法适用于求 **稠密图** 的最短距离问题。稠密图是指边数有很多的图，假设 **n** 为图的点数， **m** 为图的边数，那么一般当 **m = n2** 时该图为稠密图。朴素Dijkstra算法的时间复杂度为 **O(n2)**。该算法基于贪心算法。

# 图的存储 #

`稠密图` 一般使用 **邻接矩阵** 来存储。邻接矩阵通俗的来讲就是一个 **二维数组**。`稀疏图` 一般使用 **邻接表** 来存储。图分为 **有向图** 和 **无向图**，无向图其实是一种特殊的有向图。比如有一条从 **1** 号点到 **2** 号点的有向边，它们之间的距离为 **x**。那么 `g[1][2] = x` 表示的就是从 **1** 号点到 **2** 号点有向边的距离为 **x**。

那么如何存储无向图呢？只需要再使 `g[2][1] = x` 即可。这样就可以认为 **1** 号点到 **2** 号点之间是一条无向边，它们之间的距离为 **x**。

# 算法思路 #

1. 使用一个 `dist[]` 数组用来存储从 **源点** 到其它点的距离。初始化 `dist[1] = 0` ，其它点的 **dist** 值为 **正无穷大**（可以使用一个很大的数来表示，比如 `0x3f3f3f3f`)。

2. 找到一个尚未确定并且距离起点距离最近的点 **t**。然后标记该节点。

3. 扫描节点 **t** 的所有 **出边（t -> j)**，如果 **源点** 到 **j** 的距离比源点到 **t** 再从 **t** 到 **j** 的距离 `g[t][j]` 之和大，那么就使 `dist[j] = dist[t] + g[t][j]`。

4. 重复步骤 **2** 和 **3** 直到所有的点都被标记。

# 算法实现 #

int dijkstra() { 
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0; // 将 1 号点的距离初始化为 0
        for (int i = 0; i < n; i++) { 
            int t = -1; // t = -1 表示还没有确定
            for (int j = 1; j <= n; j++) { 
                if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
            }
    
            st[t] = true; // 将 t 加入到当前已确定最短距离的点的集合中
            // 用 t 更新其出边所到达的点到源点的最短距离
            for (int j = 1; j <= n; j++) { 
                dist[j] = min(dist[j], dist[t] + g[t][j]);
            }
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

# 例题 #

题目来源：[AcWing 849. Dijkstra求最短路 I][AcWing 849. Dijkstra_ I]

## 题目信息 ##

### 题目描述 ###

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

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

### 输入格式 ###

第一行包含整数 **n** 和 **m**。

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

### 输出格式 ###

输出一个整数，表示 **1** 号点到 **n** 号点的最短距离。如果路径不存在，则输出 **-1**。

### 数据范围 ###

1 ≤ n ≤ 500,  
 1 ≤ m ≤ 105,  
图中涉及边长均不超过10000。

### 输入样例 ###

> **3 3  
> 1 2 2  
> 2 3 1  
> 1 3 4**

### 输出样例 ###

> **3**

## 题解 ##

### 解题代码 ###

#include<iostream>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    const int N = 510;
    
    int n, m;
    int g[N][N]; // g[][] 用邻接矩阵来存储图
    int dist[N]; // dist[] 用来记录当前的点到源点的最短距离
    bool st[N];  // st[] 用来标记当前的点是否已经确定了
    
    int dijkstra() { 
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0; // 将 1 号点的距离初始化为 0
        for (int i = 0; i < n; i++) { 
            int t = -1; // t = -1 表示还没有确定
            for (int j = 1; j <= n; j++) { 
                if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
            }
            
            st[t] = true; // 将 t 加入到当前已确定最短距离的点的集合中
            // 用 t 更新其出边所到达的点到源点的最短距离
            for (int j = 1; j <= n; j++) { 
                dist[j] = min(dist[j], dist[t] + g[t][j]);
            }
        }
        
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }
    
    int main() { 
        scanf("%d%d", &n, &m);
        
        memset(g, 0x3f, sizeof g);
        while (m--) { 
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = min(g[a][b], c);  // 因为存在重边，所以只存储最短的一条边即可
        }
        
        int t = dijkstra();
        
        printf("%d\n", t);
        
        return 0;
    
    }

--------------------

> 未完待续，持续更新中……  
> ![20210304224915307.png][]

[Link 1]: https://ac-fun.blog.csdn.net/article/details/114187177
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 849. Dijkstra_ I]: https://www.acwing.com/problem/content/851/
[20210304224915307.png]: /images/20221023/b392e634c5be4830a716caec6208bfc9.png