本次笔记内容：
7.1.1 概述
7.1.2 无权图的单源最短路
7.1.3 有权图的单源最短路
7.1.3-s 有权图的单源最短路示例
7.1.4 多源最短路算法
最短路径问题
最短路径问题的抽象
问题分类
无权图的单源最短路算法
有权图的单源最短路算法
负值圈（negative-cost cycle）
Dijkstra算法
Dijkstra时间复杂度讨论
多源最短路算法
Floyd算法
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。
这条路径就是两点之间的最短路径（Shortest Path）；
第一个顶点为源点（Source）；
最后一个顶点为终点（Destination）。
单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径：
（有向/无向）无权图
（有向/无向）有权图
多源最短路径问题：求任意两顶点间的最短路径
按照递增（非递减）的顺序找出各个顶点的最短路。实际上就是广度优先搜索算法（BFS）。
dist[W] = S到W的最短距离
dist[S] = 0
path[W] = S到W的路上经过的某顶点
假设上述图用邻接表存储，上述算法的时间复杂度为
T
=
O
(
∣
V
+
E
)
T=O(|V|+|E|)
T=O(∣V∣+∣E∣)。
如上图，如果存在负值圈（negative-cost cycle），则进入无限循环。因此，我们的最短路算法都不考虑存在负值圈的情况。
算法思路依旧是按照递增（非递减）的顺序找出各个顶点的最短路。
这个算法不能解决有负边的情况。
（1）直接扫描所有未收录顶点：O(|V|)
2
T=O(|V|^2+|E|)
T=O(∣V∣2+∣E∣)
对于稠密图效果好（E与V^2同一数量级）
（2）将dist存在最小堆中：O(log|V|)
更新dist[W]的值：O(log|V|)
l
o
g
T=O(|V|log|V|+|E|log|V|)=O(|E|log|V|)
T=O(∣V∣log∣V∣+∣E∣log∣V∣)=O(∣E∣log∣V∣)
对于稀疏图效果好（E与V同一数量级）
Dijkstra例题我已在运筹学里学过多次，所写项目也有所应用，示例不再记录了。
如图是Dijkstra的例题，现在的状态是刚刚收录V_5，准备访问V_5的邻接点。
方法1：直接将单源最短路算法调用|V|遍。
3
×
T=O(|V|^3+|E| \times |V|)
T=O(∣V∣3+∣E∣×∣V∣)
对稀疏图效果好
方法2：Floyd算法
T=O(|V|^3)
T=O(∣V∣3)
对于稠密图效果好
如上图，D[i][j]逐步将各个点收录，求包含已收录点的最短距离。
如上图，Floyd算法的时间复杂图是
T=O(∣V∣3)。