From 520ca0ecf0fdc288cabfb8fc908536b8e255e792 Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E5=BF=83=E6=97=B7=E7=A5=9E=E6=80=A1?= Date: Sat, 1 Sep 2018 09:15:53 +0800 Subject: [PATCH] Update shortest-path.md --- docs/graph/shortest-path.md | 30 ++++++++++++------------------ 1 file changed, 12 insertions(+), 18 deletions(-) diff --git a/docs/graph/shortest-path.md b/docs/graph/shortest-path.md index 3b8237ee..ce8aa12e 100644 --- a/docs/graph/shortest-path.md +++ b/docs/graph/shortest-path.md @@ -113,8 +113,6 @@ Bellman-Ford 算法如下 总时间复杂度 $O(nm)$ **【对于最短路存在的图】** -（伪代码） - ``` relax(u, v) { dist[v] = min(dist[v], dist[u] + edge_len(u, v)); @@ -133,21 +131,19 @@ for (i = 1; i < n; i++) { ### 应用 -给一张有向图，问是否存在负权环 - -做法很简单，跑 Bellman-Ford 算法，如果有个点被 relax 成功了 n 次，那么就一定存在 +给一张有向图，问是否存在负权环。 -如果 n-1 次之内算法结束了，就一定不存在 +做法很简单，跑 Bellman-Ford 算法，如果有个点被 relax 成功了 n 次，那么就一定存在。 -### 另一种实现（优化）（SPFA） +如果 n-1 次之内算法结束了，就一定不存在。 -很多时候我们并不需要那么多无用的 relax 操作 +### 优化（SPFA） -很显然，只有上一次被 relax 的结点，所连接的边，才有可能引起下一次的 relax +很多时候我们并不需要那么多无用的 relax 操作。 -那么我们用队列来维护“哪些结点可能会引起 relax”，就能只访问必要的边了 +很显然，只有上一次被 relax 的结点，所连接的边，才有可能引起下一次的 relax。 -（伪代码） +那么我们用队列来维护“哪些结点可能会引起 relax”，就能只访问必要的边了。 ``` q = new queue(); @@ -164,17 +160,17 @@ while (!q.empty()) { } } ``` -spfa的时间复杂度**一般**在$o(mn)$,但稠密图可以随便卡掉spfa，所以考试时能不用就尽量别用。 +SPFA 的时间复杂度为 $O(km)~ (k\approx 2)$ （玄学），但 **理论上界** 为 $o(nm)$，但精心设计的稠密图可以随便卡掉 SPFA，所以考试时谨慎使用。 ## Dijkstra 算法 -Dijkstra 是个 人名 +Dijkstra 是个人名（荷兰姓氏）。 -`/'dikstra/` 或 `/'daikstra/`，来源不明，待考证 +IPA: /ˈdikstrɑ/ 或 /ˈdɛikstrɑ/。 -这种算法只适用于非负权图，但是时间复杂度非常优秀 +这种算法只适用于非负权图，但是时间复杂度非常优秀。 -也是用来求单源最短路径的算法 +也是用来求单源最短路径的算法。 ### 实现 @@ -208,8 +204,6 @@ Dijkstra 是个 人名 第二步，考虑每次加进来的结点，到他的最短路，上一步必然是第一个集合中的元素（否则他不会是第二个集合中的最小值，而且有第一步的性质），又因为第一个集合已经全部 relax 过了，所以最短路显然确定了 -（伪代码） - ``` H = new heap(); H.insert(S, 0); -- 2.11.0