普林斯顿算法讲义（三）(2)

普林斯顿算法讲义（三）(1)https://developer.aliyun.com/article/1484202

Prim 算法。

Prim 算法通过在每一步将新边附加到单个增长树上来工作：从任何顶点开始作为单个顶点树；然后向其添加 V-1 条边，始终取下一个（着色为黑色）连接树上顶点与尚未在树上的顶点的最小权重边（对于由树顶点定义的切割的跨越边）。

Prim 算法的一句描述留下了一个关键问题：我们如何（高效地）找到最小权重的跨越边？

• 懒惰实现. 我们使用优先队列来保存跨越边并找到最小权重的边。每次我们将一条边添加到树中时，我们也将一个顶点添加到树中。为了维护跨越边的集合，我们需要将从该顶点到任何非树顶点的所有边添加到优先队列中。但我们必须做更多的事情：连接刚刚添加的顶点到已经在优先队列中的树顶点的任何边现在变得不合格（它不再是跨越边，因为它连接了两个树顶点）。懒惰实现将这样的边留在优先队列中，推迟不合格测试到我们删除它们时。
  LazyPrimMST.java 是这种懒惰方法的实现。它依赖于 MinPQ.java 优先队列。
  
  
• 急切实现. 为了改进 Prim 算法的懒惰实现，我们可以尝试从优先队列中删除不合格的边，以便优先队列只包含跨越边。但我们可以消除更多的边。关键在于注意到我们唯一感兴趣的是从每个非树顶点到树顶点的最小边。当我们将顶点 v 添加到树中时，与每个非树顶点 w 相关的唯一可能变化是，添加 v 使 w 比以前更接近树。简而言之，我们不需要在优先队列中保留所有从 w 到树顶点的边 - 我们只需要跟踪最小权重的边，并检查是否添加 v 到树中需要我们更新该最小值（因为边 v-w 的权重更低），我们可以在处理 s 邻接列表中的每条边时做到这一点。换句话说，我们只保留优先队列中的一条边用于每个非树顶点：连接它与树的最短边。
  PrimMST.java 是这种急切方法的实现。它依赖于 IndexMinPQ.java 索引优先队列来执行减少键操作。
  

命题。

Prim 算法计算任何连通的边权重图的最小生成树。Prim 算法的懒惰版本使用空间与 E 成比例，时间与 E log E 成比例（在最坏情况下）来计算具有 E 条边和 V 个顶点的连通边权重图的最小生成树；急切版本使用空间与 V 成比例，时间与 E log V 成比例（在最坏情况下）。

Kruskal 算法。

Kruskal 算法按照它们的权重值（从小到大）的顺序处理边，每次添加不与先前添加的边形成循环的边作为 MST（着色为黑色），在添加 V-1 条边后停止。黑色边形成逐渐演变为单一树 MST 的树林。

要实现 Kruskal 算法，我们使用优先队列按权重顺序考虑边，使用并查集数据结构标识导致循环的边，使用队列收集最小生成树边。程序 KruskalMST.java 按照这些方式实现了 Kruskal 算法。它使用了辅助的 MinPQ.java、UF.java 和 Queue.java 数据类型。

命题。

Kruskal 算法使用额外空间与 E 成正比，时间与 E log E 成正比（在最坏情况下）来计算具有 E 条边和 V 个顶点的任何连通边权图的最小生成树。

练习

1. 证明，通过给所有权重加上一个正常数或将它们全部乘以一个正常数，不会影响最小生成树。
   解决方案. Kruskal 算法只通过 compareTo() 方法访问边权重。给每个权重添加一个正常数（或乘以一个正常数）不会改变 compareTo() 方法的结果。
   
2. 证明，如果一个图的边都有不同的权重，那么最小生成树是唯一的。
   解决方案. 为了推导矛盾，假设图 G 有两个不同的最小生成树，称为 T1 和 T2。设 e = v-w 是 G 中在 T1 或 T2 中的最小权重边，但不在两者中都存在。假设 e 在 T1 中。将 e 添加到 T2 中会创建一个循环 C。C 中至少有一条边，假设为 f，不在 T1 中（否则 T1 就是循环的）。根据我们选择的 e，w(e) ≤ w(f)。由于所有边的权重都不同，w(e) < w(f)。现在，在 T2 中用 e 替换 f 会得到一棵权重小于 T2 的新生成树（与 T2 的最小性相矛盾）。
   
3. 如何找到边权图的最大生成树？
   解决方案. 反转每条边的权重（或在 compareTo() 方法中反转比较的意义）。
   
4. 为 EdgeWeightedGraph.java 实现从输入流读取边权图的构造函数。
   
5. 确定 EdgeWeightedGraph.java 用于表示具有 V 个顶点和 E 条边的图所使用的内存量，使用第 1.4 节的内存成本模型。
   解决方案. 56 + 40V + 112E。MemoryOfEdgeWeightedGraph.java 通过假设没有缓存 Integer 值来进行经验计算—Java 通常会缓存 -128 到 127 的整数。
   
6. 给定边权图 G 的最小生成树，假设删除一个不会使 G 断开的边。描述如何在与 E 成正比的时间内找到新图的最小生成树。
   解决方案. 如果边不在最小生成树中，则旧的最小生成树是更新后图的最小生成树。否则，从最小生成树中删除边会留下两个连通分量。添加一个顶点在每个连通分量中的最小权重边。
   
7. 给定边权图 G 的最小生成树和一个新边 e，描述如何在与 V 成正比的时间内找到新图的最小生成树。
   解决方案. 将边 e 添加到最小生成树会创建一个唯一的循环。删除此循环上的最大权重边。
   
8. 为 EdgeWeightedGraph.java 实现 toString()。
   
9. 假设你实现了 Prim 算法的急切版本，但是不使用优先队列来找到下一个要添加到树中的顶点，而是扫描 distTo[] 数组中的所有 V 个条目，找到具有最小值的非树顶点。在具有 V 个顶点和 E 条边的图上，Prim 算法的急切版本的最坏情况运行时间的增长顺序是多少？如果有的话，什么时候这种方法是合适的？为什么？请解释你的答案。
   解决方案. Prim 算法的运行时间将与 V² 成正比，这对于稠密图是最佳的。
   
10. 为 PrimMST.java 实现 edges()。
    

创意问题

1. 最小生成森林。 开发 Prim 和 Kruskal 算法的版本，计算不一定连通的边权图的最小生成森林。
   解决方案。 PrimMST.java 和 KruskalMST.java 实现了这一点。
   
2. 认证。 编写一个名为check()的方法，使用以下割优化条件来验证提议的边集是否实际上是最小生成树（MST）：如果一组边是一棵生成树，并且每条边都是通过从树中移除该边定义的割的最小权重边，则这组边就是 MST。你的方法的运行时间增长率是多少？
   解决方案。 KruskalMST.java。
   

实验

1. Boruvka 算法。 开发 Boruvka 算法的实现 BoruvkaMST.java：通过将边添加到不断增长的树森林中来构建 MST，类似于 Kruskal 算法，但是分阶段进行。在每个阶段，找到将每棵树连接到另一棵树的最小权重边，然后将所有这样的边添加到 MST 中。假设边的权重都不同，以避免循环。提示：维护一个顶点索引数组，以标识连接每个组件到其最近邻居的边，并使用并查集数据结构。
   备注。 由于每个阶段树的数量至少减少一半，所以最多有 log V 个阶段。这种方法高效且可以并行运行。
   

网页练习

1. 最小瓶颈生成树。 图 G 的最小瓶颈生成树是 G 的一棵生成树，使得生成树中任意边的最大权重最小化。设计一个算法来找到最小瓶颈生成树。
   解决方案。 每个 MST 都是最小瓶颈生成树（但不一定反之）。这可以通过割性质来证明。
   
2. 最小中位数生成树。 图 G 的最小中位数生成树是 G 的一棵生成树，使得其权重的中位数最小化。设计一个高效的算法来找到最小中位数生成树。
   解决方案。 每个 MST 都是最小中位数生成树（但不一定反之）。
   
3. 迷宫生成。 使用随机化的 Kruskal 或 Prim 算法创建迷宫。
   
4. 唯一 MST。 设计一个算法来确定给定图 G 的 MST 是否唯一。
   
5. 随机生成树。 给定图 G，均匀随机生成 G 的一棵生成树。使用 Aldous 和 Broder 的以下显著定理：从任意顶点 s 开始，并进行随机游走，直到每个顶点都被访问过（在所有相邻边中均匀随机选择一条出边）。如果一个顶点以前从未被访问过，则将边添加到该顶点以形成生成树 T。那么 T 是图 G 的均匀随机生成树。预期的运行时间受限于 G 的覆盖时间，最多与 EV 成比例。
   
6. 最小权重反馈边集。 图的反馈边集是包含图中每个循环中至少一条边的子集。如果删除反馈边集的边，则结果图将是无环的。设计一个高效的算法，在具有正边权的加��图中找到最小权重的反馈边集。
   
7. 两个 MST 中边权重的分布。 假设加权有向图有两个 MST T1 和 T2。证明如果 T1 有权重为 w 的 k 条边，则 T2 也有权重为 w 的 k 条边。
   
8. 美国计算奥林匹克问题。 在一个城市中有 N 栋房子，每栋房子都需要供水。在第 i 栋房子建造井的成本为 w[i]美元，在第 i 和第 j 栋房子之间建造管道的成本为 c[i][j]。如果一栋房子建有井或者有一条管道路径通向有井的房子，那么这栋房子就可以接收水。设计一个算法来找到供应每栋房子所需的最小金额。
   解决方案.: 创建一个带有 N+1 个顶点的边权图（每个房子一个顶点加上一个源顶点 x）。包括每对顶点 i 和 j 之间的成本 c[i][j] 的边（表示潜在的管道）。包括源 s 和每个房子 i 之间成本为 w[i] 的边（表示潜在的开放井）。在这个边权图中找到一个最小生成树。
   
9. 恰好有 k 条橙色边的生成树。 给定一个边缘着色为橙色或黑色的图，设计一个线性对数算法来找到一个包含恰好 k 条橙色边的生成树（或报告不存在这样的生成树）。
   
10. 最小方差生成树。 给定一个连通的边权重图，找到一个最小生成树，使其边权重的方差最小化。
    

4.4 最短路径

原文：algs4.cs.princeton.edu/44sp

译者：飞龙

协议：CC BY-NC-SA 4.0

最短路径。

加权有向图是一个有向图，其中我们为每条边关联权重或成本。从顶点 s 到顶点 t 的最短路径是从 s 到 t 的有向路径，具有没有更低权重的其他路径的属性。

属性。

我们总结了几个重要的属性和假设。

• 路径是有方向的。 最短路径必须遵守其边的方向。
  
• 权重不一定是距离。 几何直觉可能有所帮助，但边的权重可能代表时间或成本。
  
• 并非所有顶点都需要可达。 如果 t 从 s 不可达，则根本没有路径，因此从 s 到 t 的最短路径也不存在。
  
• 负权重引入了复杂性。 目前，我们假设边的权重是正数（或零）。
  
• 最短路径通常是简单的。 我们的算法忽略形成循环的零权重边，因此它们找到的最短路径没有循环。
  
• 最短路径不一定是唯一的。 从一个顶点到另一个顶点可能有多条最低权重的路径；我们满足于找到其中任何一条。
  
• 并行边和自环可能存在。 在文本中，我们假设不存在并行边，并使用符号 v->w 来表示从 v 到 w 的边，但我们的代码可以轻松处理它们。
  

加权有向图数据类型。

我们使用以下 API 表示加权边：

from()和to()方法对于访问边的顶点很有用。DirectedEdge.java 实现了这个 API。

我们使用以下 API 表示加权有向图：

EdgeWeightedDigraph.java 使用邻接表表示实现了该 API。

最短路径 API。

我们使用以下 API 计算加权有向图的最短路径：

我们准备了一些测试数据：

• tinyEWD.txt 包含 8 个顶点和 15 条边
  
• mediumEWD.txt 包含 250 个顶点和 2,546 条边
  
• 1000EWG.txt 包含 1,000 个顶点和 16,866 条边
  
• 10000EWG.txt 包含 10,000 个顶点和 123,462 条边
  
• largeEWG.txt 包含一百万个顶点和 15,172,126 条边。
  

单源最短路径的数据结构。

给定一个加权有向图和一个指定的顶点 s，最短路径树（SPT）是一个子图，包含 s 和所有从 s 可达的顶点，形成以 s 为根的有向树，使得每条树路径都是图中的最短路径。

我们用两个顶点索引数组表示最短路径：

• 最短路径树上的边：edgeTo[v]是从 s 到 v 的最短路径上的最后一条边。
  
• 到源的距离：distTo[v]是从 s 到 v 的最短路径的长度。
  

松弛。

我们的最短路径实现基于一种称为松弛的操作。我们将distTo[s]初始化为 0，对于所有其他顶点 v，将distTo[v]初始化为无穷大。

• 边松弛。 对边 v->w 进行松弛意味着测试从 s 到 w 的已知最佳路径是否是从 s 到 v，然后沿着从 v 到 w 的边，如果是，则更新我们的数据结构。

private void relax(DirectedEdge e) {
    int v = e.from(), w = e.to();
    if (distTo[w] > distTo[v] + e.weight()) {
        distTo[w] = distTo[v] + e.weight();
        edgeTo[w] = e;
    }
}

• 
• 顶点松弛。 我们所有的实现实际上都会松弛从给定顶点指向的所有边。

private void relax(EdgeWeightedDigraph G, int v) {
    for (DirectedEdge e : G.adj(v)) {
        int w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
        }
    }
}

迪杰斯特拉算法。

戴克斯特拉算法将dist[s]初始化为 0，将所有其他distTo[]条目初始化为正无穷。然后，它重复地放松并将具有最低distTo[]值的非树顶点添加到树中，继续直到所有顶点都在树上或没有非树顶点具有有限的distTo[]值。

DijkstraSP.java 是戴克斯特拉算法的高效实现。它使用 IndexMinPQ.java 作为优先队列。

命题。

戴克斯特拉算法使用额外空间与 V 成正比，时间与 E log V 成正比（在最坏情况下）解决了带非负权重的带权有向图中的单源最短路径问题。

无环带权有向图。

我们使用术语带权有向无环图来指代无环带权有向图。

• 带权有向无环图中的单源最短路径问题。我们现在考虑一种用于查找最短路径的算法，对于带权有向无环图而言，它比戴克斯特拉算法更简单且更快。

• 它在线性时间内解决了单源问题。
  
• 它处理负边权重。
  
• 它解决了相关问题，如查找最长路径。
  

• 该算法将顶点放松与拓扑排序结合起来。我们将distTo[s]初始化为 0，将所有其他distTo[]值初始化为无穷大，然后按照拓扑顺序放松顶点。AcyclicSP.java 是这种方法的实现。它依赖于这个版本的 Topological.java，扩展以支持带权有向图。
  
• 带权有向无环图中的单源最长路径问题。我���可以通过将distTo[]值初始化为负无穷大并在relax()中改变不等式的意义来解决带权有向无环图中的单源最长路径问题。AcyclicLP.java 实现了这种方法。
  
• 关键路径法。我们考虑并行的有前置约束的作业调度问题：给定一组指定持续时间的作业，其中有前置约束规定某些作业必须在某些其他作业开始之前完成，我们如何在相同数量的处理器上安排这些作业，以便它们在最短的时间内完成，同时仍然遵守约束条件？
• 
  通过将问题制定为带权有向无环图中的最长路径问题，可以解决此问题：创建一个带权有向无环图，其中包含一个源 s，一个汇 t，以及每个作业的两个顶点（一个起始顶点和一个结束顶点）。对于每个作业，从其起始顶点到其结束顶点添加一条权重等于其持续时间的边。对于每个前置约束 v->w，从对应于 v 的结束顶点到对应于 w 的开始顶点添加一条零权重边。还从源到每个作业的起始顶点和从每个作业的结束顶点到汇添加零权重边。
  
  现在，根据从源到达的最长路径的长度安排每个作业的时间。
  
  CPM.java 是关键路径法的实现。
  

命题。

通过按拓扑顺序放松顶点，我们可以在时间复杂度为 E + V 的情况下解决带权有向无环图的单源最短路径和最长路径问题。

一般带权有向图中的最短路径。

如果(i)所有权重为非负或(ii)没有循环，则可以解决最短路径问题。

• 负循环。负循环是一个总权重为负的有向循环。如果存在负循环，则最短路径的概念是没有意义的。
• 
  因此，我们考虑没有负循环的加权有向图。
  
• 贝尔曼-福特算法。将distTo[s]初始化为 0，将所有其他distTo[]值初始化为无穷大。然后，以任意顺序考虑有向图的边，并放松所有边。进行 V 次这样的遍历。

for (int pass = 0; pass < G.V(); pass++)
   for (int v = 0; v < G.V(); v++)
      for (DirectedEdge e : G.adj(v))
          relax(e);

• 我们不详细考虑这个版本，因为它总是放松 V E 条边。
• 基于队列的贝尔曼-福特算法。可能导致distTo[]变化的唯一边是那些离开上一轮中distTo[]值发生变化的顶点的边。为了跟踪这样的顶点，我们使用一个 FIFO 队列。BellmanFordSP.java 通过维护两个额外的数据结构来实现这种方法：

• 一个要放松的顶点队列
  
• 一个顶点索引的布尔数组onQ[]，指示哪些顶点在队列上，以避免重复
  

• 负循环检测。在许多应用中，我们的目标是检查并提取负循环。因此，我们向 API 添加以下方法：
  当且仅当在所有边的第 V 次遍历后队列非空时，从源可达负循环。此外，我们edgeTo[]数组中的边子图必须包含一个负循环。因此，为了实现negativeCycle()，BellmanFordSP.java 从edgeTo[]中的边构建一个加权有向图，并在该图中查找循环。为了找到循环，它使用 EdgeWeightedDirectedCycle.java，这是第 4.3 节中 DirectedCycle.java 的一个版本，适用于加权有向图。我们通过仅在每次第 V 次边放松后执行此检查来分摊此检查的成本。
  
• 套汇检测。考虑一个基于商品交易的金融交易市场。rates.txt 中的表显示了货币之间的转换率。文件的第一行是货币 V 的数量；然后文件每行给出货币的名称，然后是转换为其他货币的汇率。套汇机会是一个有向循环，使得交换率的乘积大于 1。例如，我们的表格显示，1000 美元可以购买 1000.00 × .741 = 741 欧元，然后我们可以用我们的欧元购买 741 × 1.366 = 1,012.206 加拿大元，最后，我们可以用我们的加拿大元购买 1,012.206 × .995 = 1,007.14497 美元，获得 7.14497 美元的利润！

• 为了将套汇问题制定为负循环检测问题，将每个权重替换为其对数的负值。通过这种改变，在原问题中通过乘以边权重来计算路径权重对应于在转换后的问题中将它们相加。Arbitrage.java 通过解决相应的负循环检测问题来识别货币兑换网络中的套汇机会。

命题。

在加权有向图中，从 s 到 v 存在最短路径当且仅当从 s 到 v 存在至少一条有向路径，并且从 s 到 v 的任何有向路径上的顶点都不在负循环上。

命题。

贝尔曼-福特算法解决了给定源 s 的单源最短路径问题（或找到从 s 可达的负循环）对于具有 V 个顶点和 E 条边的任意加权有向图，在最坏情况下，时间复杂度为 E V，额外空间复杂度为 V。

问与答

Q. Dijkstra 算法能处理负权重吗？

A. 是和否。有两种已知的最短路径算法称为Dijkstra 算法，取决于一个顶点是否可以多次入队到优先队列。当权重为非负时，这两个版本是相同的（因为没有顶点会多次入队）。DijkstraSP.java 中实现的版本（允许一个顶点多次入队）在存在负边权（但没有负环）时是正确的，但其最坏情况下的运行时间是指数级的。（我们注意到 DijkstraSP.java 如果边权重为负数，则会抛出异常，以便程序员不会对这种指数级行为感到惊讶。）如果我们修改 DijkstraSP.java 以使一个顶点不能多次入队（例如，使用marked[]数组标记那些已经被松弛的顶点），那么算法保证在E log V时间内运行，但当存在负权边时可能产生错误结果。

练习

1. 真或假。将每个边权重增加一个常数不会改变单源最短路径问题的解决方案。
   解决方案。 假。
   
2. 为 EdgeWeightedDigraph.java 提供toString()的实现。
   
3. 使用第 1.4 节的内存成本模型确定 EdgeWeightedDigraph.java 用于表示具有V个顶点和E条边的图所使用的内存量。
   解决方案。 56 + 40V + 72E。MemoryOfEdgeWeightedDigraph.java 根据经验计算，假设没有缓存Integer值 - Java 通常缓存-128 到 127 的整数。
   
4. 从第 4.2 节中的DirectedCycle和Topological类中使用本节的EdgeweightedDigraph和DirectedEdgeAPI，从而实现 EdgeWeightedDirectedCycle.java 和 Topological.java。
   
5. 假设我们通过为EdgeWeightedGraph中的每个Edge创建两个DirectedEdge对象（分别在每个方向上）来将EdgeWeightedGraph转换为EdgeWeightedDigraph，然后使用贝尔曼-福特算法。解释为什么这种方法会失败得惊人。
   解决方案： 即使带权图不包含负权重环，这可能会引入负成本循环。
   
6. 如果在贝尔曼-福特算法的同一遍历中允许一个顶点被多次入队会发生什么？
   答案： 算法的运行时间可能呈指数增长。例如，考虑所有边权重均为-1 的完全带权有向图会发生什么。
   

创意问题

1. 有向无环图中的最长路径。 开发一个实现 AcyclicLP.java 的程序，可以解决带权有向无环图中的最长路径问题。
   
2. 线上的所有对最短路径。 给定一个加权线图（无向连通图，所有顶点的度为 2，除了两个端点的度为 1），设计一个算法，在线性时间内预处理图，并能在常数时间内返回任意两个顶点之间最短路径的距离。
   部分解决方案。 找到一个度为 1 的顶点 s，并运行广度优先（或深度优先）搜索以找到其余顶点出现的顺序。然后，计算从 s 到每个顶点 v 的最短路径长度，称为dist[v]。顶点 v 和 w 之间的最短路径是|dist[v] - dist[w]|。
   
3. 单调最短路径。 给定一个带权有向图，找到从 s 到每个其他顶点的单调最短路径。如果路径上每条边的权重要么严格递增要么严格递减，则路径是单调的。
   部分解决方案： 按升序松弛边并找到最佳路径；然后按降序松弛边并找到最佳路径。
   
4. Dijkstra 算法的懒惰实现。 开发一个实现 LazyDijkstraSP.java 的 Dijkstra 算法的懒惰版本，该版本在文本中有描述。
   
5. Bellman-Ford 队列永不为空。 证明如果在基于队列的 Bellman-Ford 算法中从源可达到一个负循环，那么队列永远不会为空。
   解决方案：考虑一个负循环，并假设对于循环 W 上的所有边，distTo[w] <= distTo[v] + length(v, w)。对循环上的所有边进行这个不等式求和意味着循环的长度是非负的。
   
6. Bellman-Ford 负循环检测。 证明如果在通用 Bellman-Ford 算法的第 V 次遍历中有任何边被松弛，那么edgeTo[]数组中就有一个有向循环，并且任何这样的循环都是负循环。
   解决方案：待定。
   

网络练习

1. 最优子结构性质。 证明从 v 到 w 的最短路径上的每个子路径也是两个端点之间的最短路径。
   
2. 唯一最短路径树。 假设从 s 到每个其他顶点都有唯一的最短路径。证明 SPT 是唯一的。
   
3. 没有负循环。 证明如果通用算法终止，则从 s 可达的地方没有负循环。提示：在终止时，从 s 可达的所有边都满足distTo[w] <= distTo[v] + e.weight()。将这个不等式对沿循环的所有边相加。
   
4. 前驱图。 真或假。在没有负循环的边权重有向图中执行 Bellman-Ford 时，遵循edgeTo[]数组总是会回到 s 的路径。对 Dijkstra 算法重复这个问题。
   
5. Yen 对 Bellman-Ford 的改进。 [参考] 将边分为两个 DAGs A 和 B：A 由从较低索引顶点到较高索引顶点的边组成；B 由从较高索引顶点到较低索引顶点的边组��。在 Bellman-Ford 的一个阶段中遍历所有边时，首先按顶点编号的升序（A 的拓扑顺序）遍历 A 中的边，然后按顶点编号的降序（B 的拓扑顺序）遍历 B 中的边。在遍历 A 中的边时，SPT 中从具有正确distTo[]值的顶点开始并且仅使用 A 中的边的任何路径都会得到正确的distTo[]值；B 也是如此。所需的遍历次数是路径上 A-B 交替的最大次数，最多为(V+1)/2。因此，所需的遍历次数最多为(V+1)/2，而不是 V。
   
6. 替换路径。 给定具有非负权重和源 s 以及汇 t 的边权重有向图，设计一个算法，找到从 s 到 t 的最短路径，该路径不使用每条边 e。你的算法的增长顺序应为 E V log V。
   
7. 道路网络数据集。

• 来自DIMACS 挑战。这里是每个州的所有道路。
  
• rome99.txt 是罗马的有向道路网络的大部分数据，来自DIMACS 挑战。该图包含 3353 个顶点和 8870 条边。顶点对应道路交叉口，边对应道路或道路段。边的权重是以米为单位的距离。
  
• NYC.txt 是纽约市的无向道路网络。该图包含 264346 个顶点和 733846 条边。它是连通的，包含平行边，但没有自环。边的权重是旅行时间，且严格为正。
  

8. 互联网路由。 OSPF（开放最短路径优先）是互联网路由中广泛使用的协议，使用了迪杰斯特拉算法。RIP（路由信息协议）是另一种基于贝尔曼-福特算法的路由协议。
   
9. 具有跳过一条边的最短路径。 给定具有非负权重的边权重有向图，设计一个 E log V 算法，用于找到从 s 到 t 的最短路径，其中您可以将任意一条边的权重更改为 0。
   解决方案。 计算从 s 到每个其他顶点的最短路径；计算从每个顶点到 t 的最短路径。对于每条边 e = (v, w)，计算从 s 到 v 的最短路径长度和从 w 到 t 的最短路径长度的和。最小的这样的和提供了最短的这样的路径。
   
10. 无向图中的最短路径。 编写一个程序 DijkstraUndirectedSP.java，使用迪杰斯特拉算法解决非负权重的无向图中的单源最短路径问题。
    
11. 弗洛伊德-沃舍尔算法。 FloydWarshall.java 实现了弗洛伊德-沃舍尔算法，用于全对最短路径问题。其时间复杂度与 V³ 成正比，空间复杂度与 V² 成正比。它使用了 AdjMatrixEdgeWeightedDigraph.java。
    
12. 随机贝尔曼-福特算法。 [参考资料] 假设我们在 Yen 算法中均匀随机选择顶点顺序（其中 A 包含所有从排列中较低顶点到较高顶点的边）。证明预期的通过次数最多为(V+1)/3。
    
13. 苏尔巴勒算法。 给定具有非负边权重和两个特殊顶点 s 和 t 的有向图，找到从 s 到 t 的两条边不相交的路径，使得这两条路径的权重之和最小。
    解决方案。 这可以通过巧妙地应用迪杰斯特拉算法来实现，即苏尔巴勒算法。
    

5. 字符串

原文：algs4.cs.princeton.edu/50strings

译者：飞龙

协议：CC BY-NC-SA 4.0

概述。

我们通过交换字符串来进行通信。我们考虑经典算法来解决围绕以下应用程序的基本计算挑战：

• 5.1 字符串排序 包括 LSD 基数排序、MSD 基数排序和用于对字符串数组进行排序的三向基数快速排序。
  
• 5.2 Trie 描述了用于实现具有字符串键的符号表的 R-way trie 和三向搜索 trie。
  
• 5.3 子字符串搜索 描述了在大段文本中搜索子字符串的算法，包括经典的 Knuth-Morris-Pratt、Boyer-Moore 和 Rabin-Karp 算法。
  
• 5.4 正则表达式 介绍了一种称为 grep 的基本搜索工具，我们用它来搜索不完全指定的子字符串。
  
• 5.5 数据压缩 介绍了数据压缩，我们试图将字符串的大小减少到最小。我们介绍了经典的 Huffman 和 LZW 算法。

普林斯顿算法讲义（三）(3)https://developer.aliyun.com/article/1484208