石田保辉(App算法动画图解开发者) 宫崎修一 (京大教授)

0 算法基本

01 什么是算法

算法是解决问题的步骤。(食谱)

选择排序的过程 :

• 先从有 n 个数字的数组里找到最小的数字 , 与最左边的数字交换顺序
• 这个最小的数字在第一位不再移动
• 然后在剩下的数字里找到最小数 , 与左边第二个数字交换顺序
• 这样进行了 n 轮交换 , 所有的数字都从小到大排列

计算机擅长高速执行一些基本命令 (加法或在指定的内存地址上保存数据等)，但无法执行复杂的命令。
排序对计算机来说就是复杂的操作。
如何设计算法来解决这个排序问题，也就等同于构思如何搭配组合计算机可以执行的那些基本命令来实现这个操作。

如何选择算法 : 一般我们重视算法的运行时间

不同算法的运行时间 :

• 全排列 : n!
• 选择排序 :

02 运行时间的计算方法

如何求得数据的量与运行时间的关系 ?

上述选择排列的运行时间计算公式 :

简化之后

符号的含义 : “忽略重要项以外的内容” , Order , 这里表示运行时间最长为多少 , 直观地表现算法的时间复杂度
选择排序的复杂度 :
快速排序的复杂度 :

03 算法的特征

有穷性 Finiteness

算法的有穷性是指算法必须能在执行有限个步骤后终止

确切性 Definiteness

算法的每个步骤必须有确切的定义

输入项 Input

一个算法有0个或多个输入 , 以刻画运算对象的初始情况 , 所谓 0 个输入是指算法本身定出了初始条件

输出项 Output

一个算法有一个或多个输出 , 以反映对输入数据加工后的结果。没有输出的算法是毫无意义的

可行性 Effectiveness

算法中执行的任何计算步骤都是可被分解为基本的可执行的操作步 , 即每个运算步都可以在有限时间内完成
(也叫有效性)

1 数据结构

11 什么是数据结构

数据存储于计算机的内存中。决定了数据顺序和位置关系的便是 “数据结构” 。
选择合适的数据结构可以提高内存的利用率。
本章会讲 7 种数据结构。由于数据在内存中是呈线性排列的 , 但是我们会使用指针等道具 , 构造出类似”树形”的复杂结构。参考 : 42 广度优先搜索

12 链表

1. 链表 : 添加和删除比较方便 , 查找 (访问) 耗费时间。
2. 每一个数据都有一个指向下一个数据的内存地址的”指针”。
3. 链表中 , 数据一般都是分散存储在内存中的 , 无须存储在连续空间里。
4. 因为分散存储 , 所以想访问数据只能从第一个数据开始 , 沿着指针顺序访问。
5. 添加 (插入) 数据 : 只需要改变添加位置前后的指针指向即可
   
6. 删除数据 : 同添加相同 , 改变指针的指向即可
   
7. 上图中 Yellow 本身还存储在内存中 , 但是不管从哪里都无法访问。所以不用特意删除。今后需要用到 Yellow所在的存储空间时 , 用新数据覆盖就可以了。
8. 链表操作的时间复杂度 : ( n为数据量 )
   若从头部开始查找 , 目标数据在链表最末尾的话需要的时间是 : O(n)<br />添加及删除数据只需要改变两个指针的指向 , 耗费的时间与 n 无关。需要的时间是 : O(n)
   参考 : 31 线性查找
9. 除上述基本链表还有几种扩展方便的链表。上述的链表在尾部没有指针。若在尾部使用指针并指向链表头部的数据 , 就可以将链表变成环形。 “循环链表” / “环形链表” (想保存数量固定的最新数据时使用)
   
10. 上述的每个数据都只有一个指针 , 可以把指针设为两个 , 并让他们分别指向前后数据。 “双向链表” 可以从前往后遍历或从后往前遍历。双向链表的缺点是 : 指针数增加导致内存需求增加 / 添加删除数据需要改变更多的指针指向。
    

13 数组

1. 数组也是数据呈线性排列的一种数据结构。与链表不同 , 访问数据简单 , 添加和删除耗费时间。
2. 数据是有索引的 , 存储在内存的连续空间内。
   
3. 因为通过连续空间存储 , 所以每个数据的内存地址都可以通过数组下标算出。因此可以借此直接访问目标数据。( 这叫做”随机访问” ) 查找的时间复杂度 : O(1)
4. 添加 O(n) : ①在数组末尾增加空位 ②把已有数据一个个往后挪 ③在腾出来的位置上写入新数据
5. 删除 O(n) : ①删掉目标数据 ②把后面的数据一个个往前移 ③删掉末尾多余的空间
6. 链表和数组的操作复杂度比较 : (根据哪种操作更频繁来选择数据结构) | | 访问 (查找) | 添加 (插入) | 删除 | | —- | —- | —- | —- | | 链表 | 慢 | 快 | 快 | | 数组 | 快 | 慢 | 慢 |

14 栈

1. 栈是一种数据呈线性排列的数据结构。栈只能访问最新添加的数据。
2. 添加数据 (入栈) : 只能放在最上面
3. 取出数据 (出栈) : 只能从最上面拿出
4. 后进先出 ( “LIFO” )
5. 在栈中 , 添加和删除数据只能在一端进行 , 访问数据只能访问到顶端的数据。要想访问中间的数据 , 必须通过出栈操作将目标数据移到栈顶才行。
6. 只需要访问最新数据时 , 选用栈作为数据结构。
7. 应用实例 : 比如 （AB（C（DE）F）（G（（H）I J）K）） 读取表达式时。左括号入栈 , 中间的数一直入栈 , 遇到右括号就将匹配的左括号为止的数出栈。
   参考 : 43 深度优先搜索

15 队列

1. 队列中的数据呈线性排列。与栈相似 , 但是队列的添加删除操作是分别在两端进行。
2. 添加 (入队) : 数据添加在最上面
3. 删除 (出队) : 数据从最下面取出
4. 先进先出 ( “FIFO” )
5. 队列不能直接访问位于中间的数据 , 必须通过出队操作将目标数据变成首位后才能访问。
6. 队列应用范围广 , 思路是 : “先来的数据先处理“
   参考 : 42 广度优先搜索

16 哈希表

1. 哈希表是一种数据结构 , 在参考 : 53 哈希函数中讲解 , 可以使数据的查询效率得到显著提升。
2. 本质上是 数组+链表 的一种数据结构
3. 哈希表存储的是由键 (key) 和值 (value) 组成的数据。比如以人名作为键 , 性别作为值。
   为了和哈希表对比 , 先将这些数据存在数组中。
   
4. 右边是长度为 6 的数组。数组的查询方式是 : 从头开始线性查找。( 比较耗时, O(n) ) 参考 : 31 线性查找
5. 哈希表可以解决上述问题。
6. 哈希表存储 :
   ①使用哈希函数计算上图 Joe 的键 , 得到哈希值( “4928” )
   ②将得到的哈希值除以数组长度 (这里为5) 取余 (“mod运算“) 结果为 3
   ③存进 3 号箱子中
   ④存储位置重复的情况 (冲突) , 使用链表在已有数据的后面继续存储
   
7. 哈希表查询 :
   ①算出 Dan (待查询数据的键) 的哈希值 , 进行 mod运算 , 结果为 4 , 得知它存储在 4 号箱中。
   ②若 4 号箱的数据的键是 Dan , 则取出 值 M , 否则按链表顺序往下查询 (此处是线性查找)
8. 哈希冲突的解决办法 : 使用链表存储
9. 如果数组的空间太小 , 使用时很容易发生冲突 , 线性查找的使用频率也非常高。
   反过来如果数组的空间太大 , 就会出现很多空箱子 , 造成内存浪费。
   因此 , 给数组设定合适的空间非常重要。
10. 这种解决冲突的办法叫做 “链地址法“ , 除此之外还有几个解决冲突的办法。
    “开放地址法” : 当冲突发生时 , 立刻计算出一个候补地址 (数组上的位置) 并将数据存进去。如果仍有冲突 , 继续计算下一个候补地址 , 直到有空地址为止。可以通过多次使用哈希函数或”线性探测法”等方法计算候补地址

17 堆

1. 堆是一种图的树形结构 , 用于实现优先队列 (Priority queue)。树形结构的详细讲解
2. 优先队列是一种数据结构 , 可以自由添加数据 , 但取出时要从最小值开始顺序取出。
3. 堆的树形结构中 , 数据存储在各个顶点 (node) 中。参考 : 41 什么是图 参考 : 42 广度优先搜索
4. 堆的示例 :
   ①每个结点最多有两个子结点 , 树的形状取决于数据的个数。
   ②结点排列顺序为从上至下 , 同行中从左至右。
   
5. 存储数据的原则 : 子结点必须大于父节点。因此 , 最小值在顶端的根结点。
6. 添加 O(logn) :
   ①把新数据放在最下行最左的位置 (没有空间时就再往下另起一行)
   ②根据子结点必须大于父结点的原则调整位置
   
7. 删除 O(1) +重构 O(logn) : (重构复杂度与树高度成正比 , 树的高度为log2n )
   ①直接从根结点取出数据
   ②取出之后堆的结构需要调整 , 将最后的数据移到最顶端
   ③如果子结点的数小于父结点 , 则将父结点与左右两个子结点较小的一个交换位置
   ④重复③直到所有数据都符合规则
   
8. 如果需要频繁地从数据中取出最小值 (最大值) , 选用堆来操作。比如45 狄克斯特拉算法 , 每一步需要从候补顶点中选择距离起点最近的那个顶点 , 此时选用堆。

18 二叉查找树

1. 也叫二叉搜索树、二叉排序树 , 是一种采用了图的树形结构的数据结构。
   参考 : 41 什么是图 参考 : 42 广度优先搜索
2. 二叉查找树的示例 : (每个结点最多有两个子结点)
   
3. 性质 :
   ①每个结点均大于其左子树上的任意一个结点
   ②每个结点均小于其右子树上的任意一个结点
4. 根据上述性质得到结论 :
   ①整个二叉查找树的最小结点要从顶端开始 , 往左下的末端寻找。
   ②整个二叉查找树的最大结点要从顶端开始 , 往右下的末端寻找。
5. 添加 :
   ①从根结点开始寻找添加数据的位置
   ②与当前结点比较 , 比当前结点小则左移 , 比当前结点大则右移
   ③重复② , 直到下面再没有结点 , 此时作为把新数据作为新结点添加到下方
6. 删除 :
   ①如果需要删除的结点没有子结点则直接删除
   ②如果有一个子结点 , 先删除目标结点 , 然后把子结点移到被删除结点的位置

③如果有两个子结点 , 先删除目标结点 , 然后在被删除结点的左子树中寻找最大结点 (或者右子树的最小结点), 移到被删除结点的位置。如果需要移动的结点还有子结点 , 就递归执行前面的操作。参考 : 74 递归

1. 查找 : 与添加一样 , 从顶端开始查找、比较
2. 二叉查找树是二分查找算法思想的树形结构体现。32 二分查找
3. 查找或添加时 , 核心操作是与当前结点数据大小的比较 , 比较的次数取决于树的高度。
   如果树的形状均衡 , 则比较和移动的次数最多是 log2n , 因此复杂度为 O(logn) 。
   但树形状朝单侧纵向延伸的话 , 树就会变得很高 , 复杂度变成 O(n) 。
4. 修正二叉查找树的形状可以显著提升查找效率。如 “平衡二叉查找树”
5. 可以把二叉查找树的子结点树扩展为 m 个( , 预先设定好的常数 ) , 像这种子结点数可以自由设定 , 形状均衡的树叫做 B树。

2 排序

21 什么是排序

• 排序 : 从小到大。
• 实例 : 邮箱里未读邮件可以按时间顺序或发件人排序。
• 当数据量非常大时 , 如何设计高效率的排序算法就是解决问题的关键。

22 冒泡排序 O(n2)

1. 冒泡排序本质上是重复一个操作 : “从序列右边开始比较相邻两个数字 , 根据结果交换这两个数的位置“
   在这个过程中 , 数字会像泡泡一样从右往左浮到序列顶端。
   
2. 完成第一轮操作后 , 整个序列的最小值被移至序列顶端 (最左) , 然后进行下一轮操作。因此 , 第一轮需要 n-1 次 , 第二轮需要 n-2 次 , 如此反复 , 总的比较次数为 。这个比较次数恒定为该值 , 与输入数据的排列顺序无关。但是交换次数与排列顺序有关。如果输入数据是从大到小排列 , 每次比较数据时都会交换。因此复杂度为 。

23 选择排序 O(n2)

1. 选择排序本质上是重复一个操作 : “从待排序的数据中寻找最小值 , 将其与序列最左边的数字交换”
2. 在序列中寻找最小值时使用的是线性查找 参考 : 31 线性查找

3. 示例 :

4. 与冒泡排序相同 , 因此 , 第一轮需要 n-1 次 , 第二轮需要 n-2 次 , 如此反复 , 总的比较次数为 。每轮中交换数字的次数最多为一次 , 如果数据是从小到大排序 , 就不需要进行任何交换。因此复杂度与与冒泡排序相同都为 。

24 插入排序 O(n2)

1. 插入排序是一种从序列左端开始 , 依次对数据进行排序的算法。
2. 思路 : 左侧为已归位数据 , 右侧是未归位数据。”从右侧取出一个数据 , 放到左侧内合适的位置” 的操作。
   
   …
   
3. 插入排序中 , 需要将从右侧取出的数据与左边的数字进行比较。如果左边的数字更小 , 则不需要继续比较和交换。如果左边的数字比较大 , 则需要不停地比较大小和交换位置 , 直到它到合适的位置。当输入数据按从大到小排列时 , 运行时间最长 , 第一轮需要比较+交换1次 , 第二轮需要比较+交换2次 , … , 因此时间复杂度为 。

25 堆排序 O(nlogn)

1. 堆排序的特点是利用了数据结构 —- 堆。参考 : 17 堆
2. 示例 :
   ①首先构建堆 , 最大的数放在根结点 , 从右至左变小排列 (降序排列)
   ②取出根结点 (最大值) , 重构堆
   ③重复操作② , 直到堆变空为止
   
   
   
3. 堆排序需要一开始将 n 个数据存入堆中 , 所需时间为 O(nlogn) 。插入一个数据需要时间 O(logn) 。
   每轮取出最大的数据并重构堆需要时间 O(logn) , 由于总共有 n 轮 , 所以重构后排序的时间也是 O(nlogn) 。因此整体来看堆排序的复杂度是 O(nlogn) 。
4. 补充 : 一般来说需要排序的数据都存储在数组中。这次使用了堆 , 但实际上也相当于将堆嵌入到包含了序列的数组中 , 然后在数组中通过交换数据来进行排序。这是强行在数组中使用了堆结构。
   

26 归并排序 O(nlogn)

1. 归并排序算法会把序列分成长度相同的两个子序列 , 当无法继续往下分时 (即每个子列只剩一个数据时) , 就对子序列进行归并。
2. 归并 : 把两个排好序的子序列合并成一个有序序列。归并会一直重复执行 , 直到所有子序列都合成一个整体。
3. 示例 :
   ①把序列分割到不能再往下分割
   ②合并时把数字按顺序排列
   ③合并有多个数的子序列时 , 先比较首位数 , 在移动较小数
   ④递归执行③ , 直到合成一个整体为止
   
   
   
4. 归并排序中 , 分割序列花费的时间不算在运行时间里 (可以当成序列本来就是分割好的) 。合并两个已经排好序的子序列时 , 只需重复比较首位数据大小并移动较小的数据 , 因此只需花费与子序列的长度相应的运行时间。所以说 , 完成一行归并的时间取决于这一行的数据量。
5. 每一行都是 n 个数据 , 所以每行的运行时间都是 O(n) 。
   将长度为 n 的序列对半分割到只有一个数据为止时 , 可以分成 log2n 行 , 因此总共有 log2n 行。所以总的运行时间为 O(nlogn) , 与前面的堆排序相同。

27 快速排序 O(nlogn)~O(n2)

1. 快速排序算法首先会在序列中随机选择一个基准值 (pivot) , 然后将除了基准值以外的数分为 “比基准值小的数” 和 “比基准值大的数” 两个类别 , 将其排成
   [ 比基准值小的数 ] 基准值 [ 比基准值大的数 ]
   然后 , 对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序。
2. 示例 :
   ①从序列中随机选择一个基准值
   ②将基准值与其他数比较 , 小于基准往左移 , 大于则右移
   ③将基准值插入序列
   ④对于左右两边的子序列重复进行①~③的操作
   ⑤只有在子问题里只剩一个数字的时候 , 排序才算完成
   -
   ---
   
3. 快速排序是一种 “分治法” , 将原本问题分成两个子问题 , 然后再分别解决这两个子问题。
   在解决子问题时再次快速排序。像这样再算法内部继续使用该算法的现象被称为 “递归”。
   上述归并排序也可以看作是一种递归的分治法。参考: 74 汉诺塔(递归)
   归并排序和快速排序的比较
4. 分割子序列时需要选择基准值 , 如果每次选择的基准值都能使这两个子序列的长度为原来的一半 , 那么快排的运行时间也和归并一样 , 都为 O(nlogn) 。如果像下图一样一行行地展现根据基准值分割序列的过程 , 那么一共分割 log2n 次 , 所以共有 log2n 行。
   
5. 上图中 , 每行中每个数字都需要和基准值比较大小 , 因此每行所需的运行时间为 O(n) 。所以整体复杂度为O(nlogn) 。
   如果运气不好 , 每次都选择最小值作为基准值 , 那么每次都需要把其他数据移到基准值的右边 , 递归执行 n 次 , 运行时间就成了 , 这样操作就和选择排序一样了。此外，如果数据中的每个数字 被选为基准值的概率都相等，那么需要的平均运行时间为 O(nlogn) 。

3 数组的查找

31 线性查找

1. 线性查找 : 在数组中从上至下查找数据的方法。与二分查找不同 , 即使数据没有按顺序存储 , 也可以应用线性查找。
2. 线性查找需要从头开始不断地按顺序检查数据 , 因此在数据量大且目标数据靠后 , 或目标数据不存在时 , 比较次数很多很耗时。复杂度为 O(n) 。

32 二分查找

1. 与线性查找不同 , 二分查找只能查找已经排好序的数据。通过比较数组中间的数据与目标数据的大小 , 得知目标数据在数组的左边或右边。比较依次就可以把查找范围缩小到一般。重复执行该操作就可以找到数据或者得出数据不存在的结论。
2. 二分查找利用已经排好序的数组。数据量为 n 的数组 , 长度减半 log2n 次后 , 其中便只剩一个数据了。也就是说 , 在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作 log2n 次后 , 就能找到目标数据 (若没找到则可以得出数据不存在的结论) , 因此它的时间复杂度为 O(logn) 。

33 补充说明

1. 二分查找复杂度 O(logn) 与线性查找 O(n) 相比是指数倍提升
2. 然而二分查找要求数据必须排好序 , 而线性查找不要求
3. 所以添加数据时 , 二分查找要求数据必须加到合适的位置 , 这样需要额外耗费维护数组的时间
   而线性查找要求数据直接添加到末尾即可
4. 所以 , 使用哪种查找方法应该根据查找和添加两个操作哪个更为频繁来决定

4 图的搜索

41 什么是图

• CS或离散数学中的图 :
  
• 图是可以表现数据间关系的一种数据结构。可以用于表示社会关系、人际关系等。
• 在计算机网络中 , 可以把路由器作为顶点 , 相互连接的两个路由器用边连接 , 用图来表示网络的连接关系。
  
• 加权图 : 除了只有边和顶点构成的图 , 还可以给边赋值 , 这个值叫 “权重” 或 “权” 。
  没有权的边只能表示两个顶点的连接状态 , 有权的边可以表示顶点之间的连接程度。
  “程度” : 根据图内容的不同 , 程度表示的意思也不同。计算机网络中可以用权表示通信时间。

• 有向图 : 给边加上箭头 , 表示方向性 , 也可以加上权重
• 图解决的问题 : 左图中 “从A到F权重之和最小” 的路径 , 对应实际问题 :
  ①寻找计算机网络中通信时间最短的路径
  ②寻找路线图中耗时最短的路径
  ③寻找路线图中最省车费的路径
  …
  因此只要能用图来表示上述关系 , 就可以用解决图问题的算法来解决这些看似不同的问题。
• 本章学习图的搜索方法 , 可以解决图的基本问题 —- 最短路径问题的算法。
  分为 “广度优先搜索” 和 “深度优先搜索” 。

42 广度优先搜索

广度优先搜索是一种图的搜索办法。假设一开始位于顶点 , 此时不知道图的整体结构。目的是从起点开始顺着边搜索 , 直到到达指定终点。此过程中每走到一个顶点 , 就会判断一次它是否是终点。广度优先搜索会优先从离起点近的顶点开始搜索。

步骤演示

• 从 A 出发 , 找到 G
• 将 A 直达的三个顶点 B C D 作为候补顶点 , 从中选出一个顶点 , 优先选择最早成为候补的那个顶点 , 因为 B C D 同时成为候补 , 随机选择一个 , 这里选择 B ( 此处的候补顶点是先入先出来管理的 , 使用队列作为数据结构 )

• A 变为已搜索的橙色 , 此时在 B , 将 B 直达的两个顶点 E F 作为候补顶点
• 此时 , 最早成为候补顶点的是C D , 随机选择C

• 移动到 C 上 , 将C直达的 H 作为候补顶点
• 重复操作直到到达终点 , 或所有点都被遍历为止

这个示例中搜索顺序为 : A -> B -> C -> D -> E -> F -> H -> I -> J -> K

解说

• 特征 : 从起点开始 , 从近到远进行广泛的搜索。所以 , 目标点离起点越近 , 搜索结束得越快
• 为了方便说明 , 此次使用没有闭环的图 , 但如果图中又闭环 , 其搜索步骤也是一样的

43 深度优先搜索

深度优先搜索也是对图搜索的算法。目的也是从起点开始搜索直到指定顶点或终点。 深度优先搜索会沿着一条路径不断向下搜索直到不能再继续为止 , 然后再折返 , 开始搜索下一条候补路径。 候补顶点采用后入先出的方式来管理 , 因此使用栈这个数据结构。

搜索顺序为 : A -> B -> E -> K -> F -> C -> H -> G (-> D -> I -> J -> L )

解说

• 特征 : 沿一条路径不断往下
• 与广度优先搜索的唯一一点不同 : 选择候补顶点作为下一个顶点的基准不同
• 广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候 补，所以会从离起点近的地方开始按顺序搜索；
• 而深度优先搜索选择的则是最新成为候 补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索
  

  44 贝尔曼-福特算法

  Bellman-Ford 算法 , 是在图中求解最短路径问题的算法 最短路径问题 : 在加权图指定了起点和终点的前提下 , 寻找起点到终点的路径中权重总和最小的那条

贝尔曼也 因为提出了该算法中的一个重要分类“动态规划”而被世人所熟知。

步骤

• 图中 A 为起点 , G 为终点 , 设起点的初始权重为 0
• 起初不知道需要走多远才能到达其他顶点 , 因此将起点外的顶点权重设为 正无穷 ∞
• 权重的意义 : A点到某一点的最短路径的暂定距离 , 随着计算进行 , 此值会越来越小 , 直到收敛到正确值
• 先从所有的边中选择一条 (A->B) , 分别计算两端权重 (顶点权重+边权重) , B = 9 (AB)
• 如果计算结果小于顶点的值 , 则更新 (此处由于计算结果9<∞ , 所以更新)
• 更新时需要记录计算的是从哪个顶点到该顶点的路径

• 接下来计算B->A的权重 , 9+9=18 > 0 , 现在的值更小 , 所以不更新
• 按照上述步骤选择A-C , 更新C的权重为 2
• 再选出一条边 B-C , A->C->B 使B的权重更新为 2+6=8

• 接着对所有的边进行更新操作 , 更新 边B-D 和 B-E
• 更新边 C-D 和 C-F
• 更新完所有的边 , 第一轮更新结束

• 重复对所有边的更新操作 , 直到权重不能再更新为止
• 第二轮更新 : B = 7 ; E = 8
• 第三轮更新 : 所有顶点的权重都不再更新 , 搜索结束 , A->C->D->F->G = 14

解说

设顶点数为 n , 边数为 m , 求贝尔曼福特算法的时间复杂度。(此处为n =7 , m = 12)

解 :

• 算法经过 n 轮更新就会停止 , 每轮更新里需要对各个边进行 1 次确认 ;
• 因此一轮更新花费时间 O(m) , 整体时间复杂度为 O(nm)

※ 本次讲解以无向图为例 , 两个方向都要计算。但在有向图中只按边的指向来计算即可

补充说明

• 计算最短路径时 , 边的权重代表的一般都是时间、距离或路费等 , 因此基本都是非负。不过贝尔曼福特算法即使权重为负也可以正常运行。
• 但 , 如果在一个闭环中 , 边的权重总和是负数 , 那么只要不断遍历这个闭环 , 路径的权重就能不断减小 , 导致根本不存在最短路径。 遇到这种对顶点进行 n 次更新操 作后仍能继续更新的情况，就可以直接认定它“不存在最短路径”
• 而下节将会介绍的狄克斯特拉算法，那么当输入的权重为负时还有 可能无法得出正确的答案。
  

45 狄克斯特拉算法

46 A* 算法

5 安全算法

51 安全和算法

52 加密的基础知识

53 哈希函数

54 共享密钥加密

55 公开密钥加密

56 混合加密

57 迪菲-赫尔曼密钥交换

58 消息认证码

59 数字签名

5A 数字证书

6 聚类

61 什么是聚类

62 K-means 算法

7 其他算法

71 欧几里得算法

72 素性测试

73 网页排名

74 汉诺塔

8 个人补充

81 归并排序和快速排序

当数据量越来越大时，
归并排序：比较次数少，速度慢。
快速排序：比较次数多，速度快。
快速排序的优势越来越明显。

原因分析：个人认为是当数据量越来越大时，尽管归并排序的比较次数较少，但是归并排序后期的合并操作所花费的时间便越来越大，合并操作对整体的效率影响越来越明显，包括后面大量数据的赋值操作等。所以当数据量变大时，不需要专门合并的快速排序的优势就变得越发明显。

C语言实验 : 归并排序和快速排序的运行时间比较

82 五大常用算法

分治
贪婪
动态规划
回溯
穷举