【学习笔记】最短路

# $\text{Floyd}$ $\text{Floyd}$是最暴力的最短路算法，具体思路为枚举中转点，然后枚举另外两个点，用中转点去松弛枚举的两个点。 由于算法特性，常常使用**邻接矩阵**来存放图的信息。又由于是三层枚举，所以复杂度为$O(n^3)$，并且可以得到**任意两点间的最短路长度**。对于200以下的小数据是非常不错的选择。 **注意：** 1. 由于是邻接矩阵存边，所以建边$(u,v)=w$的时候，应该使用 $dis[u,v]=\min\ (dis[u][v],\ w)$的方法，**否则可能会导致之前边的信息被覆盖**。 2. 一开始必须先把$dis[u][v]$数组**初始化**，将到自己的距离设为$0$，否则设为$\text{INF}$，输入完成之后再开始松弛。 3. 枚举的时候，应该**先枚举中转点**，这是由算法特性决定的。并且二层枚举的时候，$j$只用枚举到$i$即可，因为$dis[u][v]$是对称的，所以其余的枚举实际上没什么用。这样可以降低常数。 ```cpp void floyd() { for(int h = 1; h <= v; h++) // attention! for(int i = 1; i <= v; i++) for(int j = 1; j < i; j++) if(G[i][j] > G[i][h] + G[h][j]) G[i][j] = G[j][i] = G[i][h] + G[h][j]; return; } int main() { for(int i = 1; i <= v; i++) for(int j = 1; j < i; j++) G[i][j] = G[j][i] = 0x3f3f3f3f; for(int i = 1; i <= e; i++) { int a, b, w; scanf("%d%d%d", &a, &b, &w); G[a][b] = min(G[a][b], w); // attention! G[b][a] = G[a][b]; } floyd(); return 0; } ``` # $\text{Dijsktra}$ (堆优化) **算法描述**：建立一个以路径长为关键字的小根堆优先队列q，初始化 dis[s] = 0, 将数对$(s,0)$加入优先队列，每次从优先队列中取出当前最短路径估计值最小的点$u$，并对其能到达的店$v$进行松弛，若松弛成功就将更新后的$(v,dis[v])$加入优先队列。重复上述操作，直到优先队列为空。 朴素的 Dijsktra 复杂度为$O(n^2)$，堆优化以后可以跑到$O(nlogn)$。 # $\text{SPFA}$ **算法描述**：建立一个队列q，每次从队首取出节点$u$，并且用$u$当前的最短路径估计值对所有能够到达的点$v$进行松弛。如果松弛能够进行，并且$v$不在队列当中，就把$v$放入队尾。重复上述操作，直到队列为空。 复杂度约为$O(kE)$，其中$k\approx2,E$表示边数。 SPFA 算法可以判断是否出现负环，具体做法为：记录每个点到源点的最短路径上**所包含的点数** cnt，初始化 **cnt[s] = 1**（源点也被包含在内），每次松弛成功就对 cnt 进行更新，也就是 cnt[v] = cnt[u] + 1，如果出现了 cnt[u] > n 的情况，也就是说最短路径上出现了重复的点，很明显就出现了负环。这种算法显然是比以前判断出队次数要快得多的。 # 最短路树 未完待续…