本文共 1816 字，大约阅读时间需要 6 分钟。

单点最短路，非负权：

Dijkstra算法：

动态规划思想，时间O(N*N)

维护一个最短路数组dis，不断更新。 维护一个vis数组，选择dis最小且未访问节点。 若需要打印最短路径，则维护一个father数组，记录前驱节点。

---

单点最短路，负权无环路：

Bellman-Ford算法：

动态规划思想，时间O(NNN)

维护一个dis数组，代表到点i的最短路。 更新公式为，dis[i] = min{dis[i],dis[j]+e[j][i]} 对于每个点，枚举其他点是否可以对当前点更新。 最多进行N-1轮次更新即可，也可设着flag，当没有更新出现时跳出。

实现上：

邻接表复杂度O(NE)

邻接矩阵复杂度O(NN*N) 酌情使用

判断负权回路，若第N次仍然能更新dis值，则存在负权回路。

---

SPFA算法，队列版Bellman-Ford算法：

时间O(km)，k为点平均入队时间，m为边数量，通常k=2。 有最短路更新，才需要将更新点入队，减少不必要的计算。 实现上： 邻接表更适合。

判断负权回路，若一个顶点入队N次，则有负权回路。

---

所有点最短路，负权无环路：

Floyd算法：

动态规划思想：

最外层循环枚举中间节点k， 内部两层循环枚举起始节点和终止节点i，j， 判断是否可以通过k修改i，j的最短路径，时间O(NNN) floyd算法适合邻接矩阵。

一开始会对floyd原理有些不理解：

难道不会出现 dp[i][x1] + dp[x1][j] < dp[i][j] 即中间节点更新了【i，j】 然后再出现dp[i][x2] + dp[x2][x1] < dp[i][x1] 即中间节点更新了【i，x1】 这样，【i，j】就一定不是最小的，矛盾啊。

这个图如下：

i —> j i —> x1 —> j i —> x2 —> x1 ----> j

手推一遍发现，

若先出现x1更新【i，j】 那么一定会出现x1更新【x2，j】 然后出现x2更新【i，x2】 这样【i，j】还是最小的。

$这样对floyd最外层循环k有了更深的理解，$

$k不仅表示中间节点id，同样还表示【i，j】中最多k-1个中间点时的最短距离。$ $按Bellman-Ford思想，这个k不会大于N。$

---

POJ1135

多米诺骨牌效应：

图中节点为关键牌，图中边为普通牌，求最后一个倒下的关键牌或普通牌所在的边。

Dijkstra算法求每个关键牌的倒下时间为time[i]，记录最大值Max1

再求每条边倒下的最终时间，(time[i]+time[j]+Edge[i][j])/2，记录最大值Max2， 若Max2>max1则，打印between key… 否则，打印 at key…

---

ZOJ1456

最小运输费用

难点在于使用floyd后，保证最短路时路径字典序最小，

原始floyd使用path[i][j]记录倒数第二个点。 这里使用path[i][j]矩阵记录第二个节点。

---

POJ1192

最优连通子集

给定单点集V，每个点都有整数权重，找权和最大的连通块。

树dp：

根据题意，单点集V一定是一棵树，最多包含四个分支。

则题目求树中最大权联通块。 树形dp即可。

---

ZOJ1232

超级马里奥的冒险

A+1～A+B是城堡，1～A是村庄，求从A+B点到1点的最短路，现在有K双一次性鞋子，每双鞋子可以在瞬间最多走L距离，但必须停在节点上，且使用鞋子不可以横穿具有城堡属性但节点，则最小时间是？

图DP：

dp[i][j]表示到 i 点时，还剩下 j 双鞋子的最短距离。 另维护一张w表，w[i][j]表示是否可以一双鞋子到达。 SPFA填dp表即可。

---

转载地址：http://bdwji.baihongyu.com/