今天在Leetcode练习算法的时候，不禁思考一个问题，DFS和回溯算法，有什么区别呢？

先来回顾一下我们所熟知的DFS，拿FloodFill问题举例的话，先手写一个伪代码看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//int map[N][N]里面0表示海，1表示岛屿，要求一个map里面连通岛屿的个数
//bool mark[N][N]表示该位置是否被访问过
//int go[][2]表示上下左右四个方向位置转移
int counter;
void DFS(int x,int y){
    for(i in 四个方向){
        int newX=x+go[i][0];int newY=y+go[i][1];
        if(x越界 或者 y越界) continue;
        if(该点不是1) continue;
        if(该点已经被访问过) continue;
        mark[newX][newY]=true; //标记访问
        DFS(newX,newY);
    }
}
main(){
    ...
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
         	if(该点是1 并且 该点未被访问){
                counter++;DFS(i,j);
            }
        }
}

可见，传统DFS一般不会有“解空间”或者复杂解空间结构之类的说法。在之前的《算法》学习中，我一直把二者平等看待，但发现二者还是应该区别看待。DFS是一个劲的往某一个方向搜索，而回溯算法建立在DFS基础之上的，但不同的是在搜过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。状态管理是回溯的核心，回溯算法应用很多，今天就来手写三个典型的数学问题的回溯。首先，我们来看一下回溯算法的基本模板

1
2
3
4
5
6
7
8
9

result = []
def backtrack(路径, 选择列表或者选择的出发点):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

求N个元素的子集，从数学的角度，该子集的个数是2^n个，如果要输出这些子集呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums){
    vector<int> track;
    backTrack(nums,0,track); //0表示深度,track即路径
    return res;
}
void backTrack(vector<int>& nums,int start, vector<int>& track){
    res.push_back(track); //这里不用判断是否满足结束条件,每一处都是结束点
    for(int i=start;i<nums.size();i++)
    {
        //做选择
        track.push_back(nums[i]);
        backTrack(nums,i+1,track);
        //撤销选择
        track.pop_back();
    }
}

输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

vector<vector<int>>res;
vector<vector<int>> combine(int n, int k) {
    if (k <= 0 || n <= 0) return res;
    vector<int> track;
    backtrack(n, k, 1, track);
    return res;
}
void backtrack(int n, int k, int start, vector<int>& track) {
    // 到达树的底部
    if (k == track.size()) {
        res.push_back(track);
        return;
    }
    // 注意 i 从 start 开始递增
    for (int i = start; i <= n; i++) {
        // 做选择
        track.push_back(i);
        backtrack(n, k, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

输入一个不包含重复数字的数组 nums，返回这些数字的全部排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

List<List<Integer>> res = new LinkedList<>();
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。大部分回溯算法问题了，无非就是 start 或者 contains 剪枝，也没啥别的技巧了。

​ How time flies, 转眼已是八月。
2020年7月22号，我迎来了人生一个重要的转折点，即中科院计算所🏫的考核。在努力💦和运气🤞的作用下，我有幸在自己参与的第一个夏令营，就通过了，并且也是自己很想要去做的方向的很好的老师👩‍💻。过去的两周内，算是彻底松了一口气，也没有去学习什么，就去报了一个驾校🚗，看这个暑假能不能考过两个科目，其实也不算很大的事情。而过了这彻底松口气的两周，我也觉得没有规划，不开展学习和实践的生活是真的枯燥，于是决定去学点东西，去企业面试积累一点经验。
言归正传，来简单回顾一下这段时间吧。在学期内，跟着老师的进度开展课内的学习，在软工大作业验收的那几天体验了一下极限编程，也通过后端大作业进一步和中间件等技术有了头一次实操的经验。然后是准备保研，复习自己做过的项目，并且DFS般回顾一遍，不过还算好，因为都是自己亲自参与的。关于准备机考，就是把王道和算法笔记以及剑指offer的题来回刷，也没啥可以多说的。关于准备笔试，倒没怎么准备，毕竟计算机💻科学所学的知识大部分都“刻进DNA”了。
最后是定一些小flag🚩：1.继续加强算法日常练习 2.自己动手把Django&Vue构建一个比较完善的项目 3.把Andrew Ng的Deeplearning.Ai看完，如果还有空可以看看王晓捷老师的NLP介绍课程，扩展自己的认知 4.看一些边缘计算，边缘智能的论文与报告
先写到这吧~

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
 
Input&Output
输入三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。如果能平分的话请输出最少要倒的次数，否则输出"NO"。
 
Sample Input
7 4 3
4 1 3
0 0 0
 
Sample Output
NO
3

用最大公约数的角度思考，本质就是寻找一个最优化方程组的可能整数解;记录此题是因为用BFS写起来过于冗长，这种解决方法给我耳目一新的感觉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int a,b,c;
    while(cin>>a>>b>>c&&(a&&b&&c))
    {
        a/=gcd(b,c);
        if(a&1)
            cout<<"NO"<<endl;
        else
            cout<<a-1<<endl;
    }
    return 0;
}

在之前提到的五种方法，虽然把标签都归结于深度学习，但其实这一篇才是用深度网络的方式来解决降噪这个逆问题，囿于篇幅，这里就贴一个文档的链接好了。
改进Deep Image Prior进行图像降噪工作

近几年，低秩矩阵恢复（LRMR）广泛用于图像处理用途图像恢复，比如去噪、去模糊等。一幅清晰的自然图像其数据矩阵往往是低秩或者近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性。低秩矩阵恢复是将退化图像看做一组低维数据加上噪声形成的，因此退化前的数据就可以通过低秩矩阵来逼近。
设B为模糊图像，根据低秩分解有B=I+N，其中I为清晰图像，是低秩的。N为噪声具有稀疏性。

秩的行列式定义：设在矩阵A中有一个不等于0的r阶子式D，且所有r+1阶子式（如果存在的话）全等于0，那么D称为矩阵A的最高阶非零子式，数r称为矩阵A的秩，记作R（A）。并规定零矩阵的秩等于0.求解方法：对矩阵作初等行变换为行阶梯矩阵，其中非零行的个数为矩阵的秩。其物理意义矩阵中的最大不相关的向量的个数。顾名思义，低秩是指矩阵的秩比较小，而矩阵的低秩性是指矩阵的秩相对矩阵的行数或列数而言很小。

低秩与稀疏: 低秩是指矩阵的秩较小，稀疏是指矩阵中非零元素的个数少。如果对矩阵进行奇异值分解，并把其所有奇异值排列为一个向量，那么这个向量的稀疏性便对应于该矩阵的低秩性

由矩阵秩的定义知道，若将图像看成一个矩阵，那么它的基的数量越少，基对应的线性无关向量数量就越少，矩阵的秩就越小。当它远远小于矩阵的大小的时候，图像就是低秩的。低秩矩阵的每行或者每列都可以用其他的行或者列线性表示，这说明这个矩阵包含了大量的冗余信息。利用这种冗余信息可以对确实图像信息进行恢复，可以将多出来的噪声信息进行去除，还可以对错误的图像信息进行恢复。图像处理中，rank可以理解为图像所包含的信息的丰富程度，在现实生活中，一张图片大部分是相似的。比如一张大草原的图片：可以理解为，草原是由很多草组成的，而草是相似的，所以如果全是草，那么这张图所包含的信息量是很少的的，因为可以理解为草是草的复制品。如果图片中比较突兀的成分，比如蒙古包，比如人像照片中的红眼亮点，会增加图像矩阵的秩。

我们可以利用图像的低秩性来恢复图像，首先构建融合了低秩矩阵先验的模型，再求解这个模型得到低秩的矩阵。这种基于低秩矩阵逼近（LOW-Rank Matrix Approximation,LRMA）的模型称为低秩矩阵恢复模型（LRMR）。目前，LRMR主要有鲁棒主成分分析robust PCA,RPCA）、矩阵补全（matrix completion,MC）和低秩表示（low-rank representation，LRP）等三类模式。LRMR其实就是假设给定数据矩阵D，D=A+E,其中A和E未知，但是A是低秩的。 低秩矩阵表示是将数据集矩阵D表示成字典矩阵B（也称为基矩阵）下的线性组合，即D=BZ，并希望线性组合系数矩阵Z是低秩的,其实是希望能解决一个最优化问题。

这篇文章把奇异值的意义介绍的很详细：https://www.zhihu.com/question/22237507/answer/53804902 。简而言之，奇异值分解是将矩阵分解成若干个秩一矩阵（矩阵秩为1）之和，奇异值往往对应着矩阵中隐含的重要信息，且重要性和奇异值大小正相关。

外部先验（external prior）：如果从有噪音的图片本身无法找到规律，我们也可以借助其他类似但又没有噪音的图片，来总结图片具有的固有属性。这一类方法利用的外部图片来创造先验条件，然后用于约束需要预测的图片。最有代表性的工作，就是混合高斯模型（Gaussian Mixture Model）。严格来说，基于深度学习的算法也可以归于这个类。所以这里是指传统的外部先验方式。
顾名思义，就是用多个带有权重的高斯密度函数来描述数据的分布情况。理论上来说，高斯分量越多，极值点越多，混合高斯密度函数可以逼近任意概率密度函数，刻画模型越精确，需要的训练数据也就越多。
图中的点在我们看来明显分成两个聚类。这两个聚类中的点分别通过两个不同的正态分布随机生成而来。但是如果没有GMM，那么只能用一个的二维高斯分布来描述图中的数据。如果只考虑一个高斯分布，最后能作出一个椭圆区域，这显然不太合理，毕竟肉眼一看就觉得应该把它们分成两类。

其用数学方式表示出来很简单：

例如图2的例子，很明显有两个聚类，可以定义K=2. 那么对应的GMM形式如下：

将GMM的思想和一些方法进行结合，就可以达到一定的降噪效果，比如小波分解。

从稀疏分解与稀疏表示的角度看，含噪的图像信号包括两部分，干净图像信号与噪声。由于干净的图像信号是又一定的结构的，其结构特性与原子特性相吻合，故干净图像信号是稀疏成分，通过设定稀疏表示阈值可以保留下来。而噪声是随机的，不相关，因此没有结构特性。如果能够从信号中提取出有意义的原子，则提取出的部分就作为信号。如果不能继续从信号残差中提取出有意义的原子，则认为信号残差中全部是噪声。通过这样的原理可以达到图像去噪的目的。感觉做稀疏表示降噪的比较少，看了很多资料，在知乎上看到一篇还不错的，再结合论文，今天就来讲讲K-SVD算法。

SVD

从大二上学到《矩阵论》，到今天才知道SVD可以用于图片压缩。奇异值分解是一个能适用于任意的矩阵的一种分解的方法，假设A是一个N M的矩阵，那么得到的U是一个N N的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个N M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个N N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），从图片来反映几个相乘的矩阵的大小可得下面的图片。当我们从大到小开始截断，丢弃较小的奇异值并重建图像之后，我们就能得到「压缩之后」的图像了。在Python的cv2包中有相关实现。

下面这张图就是对一张高清图片选择前五十个较大特征值进行压缩得到的小猫咪。此时，重建的图像和原图已经相当接近了。

同样的，SVD也可以进行降噪。其原理是，奇异值较小的部分，频率较低，大多不是信号而是噪声部分，将其去除后（即，只取前面频率较高的部分），就相当于进行了降噪处理。

K-means

首先申明，K-means和KNN是两个不同的算法。K-平均算法源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。这个问题将归结为一个把数据空间划分为Voronoi cells的问题。
这个问题在计算上是NP困难的，不过存在高效的启发式算法。一般情况下，都使用效率比较高的启发式算法，它们能够快速收敛于一个局部最优解。这些算法通常类似于通过迭代优化方法处理高斯混合分布的最大期望算法（EM算法）。而且，它们都使用聚类中心来为数据建模；然而k-平均聚类倾向于在可比较的空间范围内寻找聚类，期望-最大化技术却允许聚类有不同的形状。

KNN分类算法

监督学习
数据集是带Label的数据
没有明显的训练过程，基于Memory-based learning
K值含义 - 对于一个样本X，要给它分类，首先从数据集中，在X附近找离它最近的K个数据点，将它划分为归属于类别最多的一类

K-means聚类算法

非监督学习
数据集是无Label，杂乱无章的数据
有明显的训练过程
K值含义- K是事先设定的数字，将数据集分为K个簇，需要依靠人的先验知识

K-means要解决的问题是NP问题，为了避免NP问题带来的计算麻烦，算法使用迭代的方式，能以较快的速度得到一个不错的局部最优结果。字典设计问题上也存在计算量过大的问题，将其K-means这种避其锋芒，退而求其次的方法推而广之便有了K-SVD算法。
原始的K-means算法思想分四步：

1. 从N个点随机选取K个点作为质心
2. 对剩余的每个点测量其到每个质心的距离，并把它归到最近的质心的类
3. 重新计算已经得到的各个类的质心
4. 迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束

稀疏表示与字典学习

写字相对于打字而言是很麻烦的，你需要一笔一划的写，每一个笔画你都必须认真写，否则就会很丑。但在打字的时候，具体来说，拼音打字，只需要输入几个字母就能打出你想要的字，而且这些字在屏幕上显示得异常美观。而几个字母就能表示笔画复杂的文字的过程，我们就可以称之为“稀疏表示”，简而言之，它就是用少量信息来映射复杂信息的过程。从广义上来说，人类的语言文字皆为稀疏表示，用少量的象形符号排列组合就能表示无限多的含义。那么“稀疏表示”又是怎么做到的呢？答案是利用“字典”。
正是因为电脑里保存了Unicode字符库、字体库等等一系列支持软件，我们才能用几个字母来写出一个标准的漂亮的字。也正是因为人类将世界中复杂的信息分解抽象化成为符号，构成“字典”，我才能够用这一屏幕密密麻麻的小黑方块，来向你介绍什么是“稀疏表示”，什么又是字典。
而字典是有好坏之分的，好的字典有两个特点，一是在表达的时候只需要用非常稀疏（即很少）的信息，二是这些稀疏的信息通过字典的映射（可以将字典看做一个函数），准确地表达原本的含义，即误差低。简而言之，好的字典较准确地提取出了复杂信息中的抽象结构。

K-SVD

前言

这个部分应该总共会有五个part，来讲述最近的一些工作，分别小结五类图片降噪方法。降噪的本质，是要从观测值中分离噪音，保留图像。算法的关键，是要掌握并借助于图像本身独特的性质和结构。根据算法利用了什么图像性质，就可以分为许多流派了。基本上可以这么划分：滤波类， 稀疏表达类，外部先验，聚类低秩和最近很热的深度网络方法。
今天主要来学习第一类滤波算法，最知名的是BM3D算法了。这是一种相对比较传统的算法，通过设计滤波器对图像进行处理。特点是速度比较快，很多卷积滤波可以借助FFT变换来加速。近期的一些算法也结合了一些block matching来利用图片的self-similarity，效果不错。
有两种噪声算法，一种是非局部去噪方法Non-local method(NLM)，是一种空间算法，另一种transform method是一种转换算法，都在图像去噪中得到很好的效果，所以自然而然地想：同时使用两种算法效果如何？这便引出了BM3D去噪算法。

Non-Local Means

顾名思义，这是一种非局部平均算法。何为局部平均滤波算法呢？那是在一个目标像素周围区域平滑取均值的方法，所以非局部均值滤波就意味着它考虑到了图像中的所有像素，这些像素根据某种相似度进行加权平均。非局部均值滤波由Baudes提出，其出发点应该是借鉴了越多幅图像加权的效果越好的现象，那么在同一幅图像中对具有相同性质的区域进行分类并加权平均得到去噪后的图片，应该降噪效果也会越好。同时，在一个邻域中，不同位置的像素权重也不一样，考虑到复杂度搜索区域大概取21x21，相似度比较的块的可以取7x7。

Transform method

这个方法偏信号角度，比较知名的方法是小波去噪。从信号学的角度看 ,小波去噪是一个信号滤波的问题。尽管在很大程度上小波去噪可以看成是低通滤波 ,但由于在去噪后 ,还能成功地保留信号特征 ,所以在这一点上又优于传统的低通滤波器。由此可见 ,小波去噪实际上是特征提取和低通滤波的综合

BM3D

BM3D算法总体分为两大步估计，每一大步又分为三小步：相似块分组、协同滤波和聚合。Basic estimate与Final estimate，两步除Collaborative filtering不同外，其余子步骤近似。从2007年提出，它在近十年内都被认为是最好的算法。甚至目前一些论文也经常引用到这个模型。说白了，该算法通过相似判定找到与参考块相近的二维图像块，并将相似块按照组合成三维群组，对三维群组进行协同滤波处理，再将处理结果聚合到原图像块的位置。

第一大步：基础估计

第一步，搜索相似块，然后把相似的块grouping成一个个3D stack。（图像本身是2D，变成stack就成了3D）

第二步，协同滤波：先对每个三维矩阵中的二维的块进行二维变换（DCT变换）后再在矩阵的第三个维度进行一维变换，通常为Hadamard Transform。变换后采用硬阈值的方式将小于超参数(lambda_3D)的成分置为0。同时统计非零成分的数量作为后续权重的参考。最后通过在第三维的一维反变换和二维反变换得到处理后的图像块。这里会涉及到一个凸优化的硬阈值(Hard Threshold)的概念。
第三步，聚合：将这些图块逆变换后放回原位，利用非零成分数量统计叠加权重，最后将叠放后的图除以每个点的权重就得到基础估计的图像，权重取决于置0的个数和噪声强度，此时图像的噪点得到了较大的去除。

第二大步：最终估计

1、分组：基础估计已经极大地消除了噪点对于含噪原图的每个目标图块，可以直接用对应基础估计图块的欧氏距离衡量相似程度。按距离从小到大排序后取最多前MAXN1个。将基础估计图块、含噪原图图块分别叠成两个三维数组。所以这一步与第一步中不同的是这次会得到两个三维数组，一个是噪声图像形成的三维数组一个是基础估计得到的三维数组。
2、协同滤波：两个三维矩阵都进行二维和一维变换，这里的二维变换采用DCT变换。不同之处在于，用维纳滤波（Wiener Filtering）将噪声图形成的三维矩阵进行系数放缩，该系数通过基础估计的三维矩阵的值以及噪声强度得出。这一过程用如下公式表示，其中(w_p)是维纳滤波的系数：
3、聚合：与第一步中一样
相对于基础估计图，最终估计图还原了更多原图的细节。

最近真是加把劲骑士。今天复习一下最短路径，即给定图计算从起点到终点的最短路径。常用算法有Dijsktra、Bellman-ford、SPFA、Floyd算法。

Dijsktra单源最短路

基本思想：设置已访问节点S，然后每次从V-S中选择离起点s的最短路径最小的节点u，之后以u为中介，调整s到从u经过能到达的所有顶点v的最短距离，执行n次即可。简单来说，就是每次选择未访问最短距离点，选择后借助这个点开放相关边，再借助相关边更新最短路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

const int MAXV=1000;
const int INF=0x3fffffff;

int n,G[MAXV][MAXV];
int dis[MAXC];
bool vis[MAXV]={false};

void Dijstra(int s) //s means source
{
    fill(dis,dis+MAXV,INF); //慎用memset,fill为algorithm库提供的函数
    dis[s]=0;

    for(int i=0;i<n;i++)  //重复n次
    {
        int u=-1,MIN=INF; //找到dis[u]最小
        for(int j=0;j<n;j++) //找到u
        {
            if(vis[j]==false&&dis[j]<MIN)
            {
                u=j;
                MIN=dis[j];
            }
        }

        if(u==-1) return; //说明剩下的顶点和s不连通
        vis[u]=true;
        for(int v=0;v<n;v++)
        {
            //如果v没访问 且 u能到达v 且 能够达到更优的dis
            if(vis[v]==false&&G[u][v]!=INF && dis[u]+G[u][v]<dis[v])
            {
                dis[v]=dis[u]+G[u][v];
                //pre[v]=u
            }
        }
    }
}

邻接链表版的就略了，它可以一定程度减小时间复杂度，降低空间开销。
以上只是求解了最短距离，并未求解最短路径。实际上，我们添加一个pre[MAXV]数组，其中pre[v]表示从起点到顶点v的最短路径上v的上一个前驱节点。初始时，pre[i]指向自身i。最后，在更新可更新边的时候，将pre[v]确定为本次循环确定的节点u。要访问路径，从最后一个节点递归访问即可。

1
2
3
4
5
6
7
8

void DFS(int s,int v) //从终点v开始递归
{
    if(v==s){
        printf("%d\n",s);return;
    }
    DFS(s,pre[v]);
    printf("%d\n",v);
}

同时，dijsktra算法也有很多变体，比如最短路不止一条，往往会新增一个关于开销的量度：

• 给每一条边新增一个另一个维度的边权，即除了距离，还有花费，希望路上少花点钱
• 给每个点增加一个点权，希望能够搜集更多的物资
• 直接问如果有，有几条
  对于这三种，增加一个数组来存放新增的边权或者点权或者最短路径条数，然后修改优化dis[v]那个步骤即可。以第一个情况为例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  for(int v=0;v<n;v++) { if(vis[v]==false&&G[u][v]!=INF) { if(dis[u]+G[u][v]<dis[v]) { dis[v]=dis[u]+G[u][v]; cos[v]=cos[u]+cost[u][v]; //cos和dis一样，cost和G类似 } else if(dis[u]+G[u][v]==dis[v]&&c[u]+cost[u][v]<cost[v]) { cos[v]=cos[u]+cost[u][v]; } } }

而数有几条最短路,新增一个数组num，令从起点s到达顶点u的最短路径条数为num[u]，最初num[s]=1其他为0,而会引起多条最短路的情况是在u这个点可以平等选择多个点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for(int v=0;v<n;v++)
{
    if(vis[v]==false&&G[u][v]!=INF)
    {
        if(dis[u]+G[u][v]<dis[v])
        {
            dis[v]=dis[u]+G[u][v];
            num[v]=num[u];
        }else if(d[u]+G[u][v]==d[v])
        {
            num[v]+=num[u];
        }
    }
}

Bellman-Ford&SPFA

一旦出现负边权，Dijsktra算法就会失效。BF算法主要思想是设置一个数组d用来存放最短距离，同时返回一个bool值：如果其中存在从源点可达的负环，那么返回false；否则返回true，此时d中存放的值就是最短距离。

此时如果不存在从源点可达的负环那么d中所有值应该达到最优了，对所有边在判断一次，如果仍然可以松弛，就说明存在从源点可达的负环返回false。其复杂度是O(n*Edge).

1
2
3
4
5

for(each edge uTov)
{
    if(d[u]+length[uTov]<d[v]) return false;
    return true;
}

邻接链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

struct Node{
    int v,dis;
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV];
bool Bellman(int s)
{
    fill(d,d+MAXV,INF);
    d[s]=0;

    for(int i=0;i<n;i++) //循环n次
    {
        for(int u=0;u<n;u++) //遍历所有边
        {
            for(int j=0;j<Adj[u].size();j++)
            {
                int v=Adj[u][j].v;
                int dis=Adj[u][j].dis;
                if(d[u]+dis<d[v])
                {
                    d[v]=d[u]+dis;
                }
            }
        }
    }
    //判断负环
    for(int u=0;u<n;u++)
    {
        for(int j=0;j<Adj[u].size();j++)
        {
            int v=Adj[u][j].v;
            int dis=Adj[u][j].dis;
            if(d[u]+dis<d[v])
            {
                return false;
            }
        }
    }
    return true;
}

BF算法主要是在O(VE)的E上开销太大了，但其中存在很多无意义操作，通过队列优化就得到了SPFA算法，复杂度降低为O(kE),k一般不超过2.

弗洛伊德算法

全源最短路，囿于复杂度，一般一次能跑的节点不能超过200.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void Floyd()
{
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                //两者可达且可优化
                if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
}