algorithm - 在边权重为 2、3 或 5 的图上修改广度优先搜索

Question

Suppose that we are given a directed graph H = (V, E). For each edge e, the weight of the edge, w(e) is either 2, 3 or 5. Modify the BFS so that it will compute the length of the shortest path from a single source vertex s. Explain why your algorithm is correct and determine its worst-case running time (You may assume that H is represented via an adjacency list).

你会怎么做？是什么让特定权重边与任何边不同？

Answer 1

您可以考虑边之间的假想节点。因此，如果在 2 个节点之间存在长度为 2 的边。您创建一个中间节点并在它们之间添加长度为 1 的边。然后使用正常的广度优先搜索。 (您还需要为长度为 3 和 5 的节点执行此操作，添加 2 和 4 个节点)。因为你只添加了一个 O(E) 节点，所以它的复杂度是一样的。