BFS 最短路径与扭曲算法
BFS Shortest Path with a Twist Algorithm
设 G=(V,E) 为有向图。设 V 中的 s 为一个顶点。设 V 中的 k 是某个顶点，使得 k≠s。给定路径 p，将其成本定义为 p 中的边数。但是，如果一条路径经过顶点k，那么在访问过顶点k之后使用的每条边都算作5。
对于 V 中的每个 v，用 c(s,v) 表示从 s 到 v 的最便宜路径的成本。建议一个有效的
用于计算 V 中每个 v 的值 c(s,v) 的算法。
我也不会用Dijkstra算法
我最初的想法是使用单源最短路径算法。
这是我的尝试：
算法：
- 使用 BFS 计算从 s 到 v 的所有路径（未加权），将路径存储在列表中。
- 遍历列表中的每条路径，如果路径中有 k，则计算 k 之后的节点数（将其分配给变量 num），并将 4*num 添加到步骤 1 中已计算的总和.
- 选择结果数最小的路径，然后return它。
我想我可以做得更好，因为在最坏的情况下，我们将有 |V|/2 条路径，所以时间复杂度可以是 O(n^2)。
我想听听一些改进任务的建议。
非常感谢！
只能有两种类型的路径 - 通过 k 的路径和不通过 k 的路径：
s --> ... --> vs --> ... --> k --> ... --> v
现在要找到第一类路径，我们可以简单地从具有特殊条件的节点 s 进行 BFS - 如果我们碰巧到达节点 k[=20=，我们就不能去任何地方]
对于其他路径，我们可以将它们分成两部分，s --> ... --> k 和 k --> v，注意第一部分已经为第一个 BFS 所知。现在我们可以再次进行 BFS，这次是从节点 k.
现在任何 v 的最短路径 s --> v 只是 min(type1PathCost[v], type1PathCost[k] + type2PathCost[v] * 5)
设 G=(V,E) 为有向图。设 V 中的 s 为一个顶点。设 V 中的 k 是某个顶点，使得 k≠s。给定路径 p，将其成本定义为 p 中的边数。但是，如果一条路径经过顶点k，那么在访问过顶点k之后使用的每条边都算作5。
对于 V 中的每个 v，用 c(s,v) 表示从 s 到 v 的最便宜路径的成本。建议一个有效的 用于计算 V 中每个 v 的值 c(s,v) 的算法。
我也不会用Dijkstra算法
我最初的想法是使用单源最短路径算法。
这是我的尝试：
算法：
- 使用 BFS 计算从 s 到 v 的所有路径（未加权），将路径存储在列表中。
- 遍历列表中的每条路径，如果路径中有 k，则计算 k 之后的节点数（将其分配给变量 num），并将 4*num 添加到步骤 1 中已计算的总和.
- 选择结果数最小的路径，然后return它。
我想我可以做得更好，因为在最坏的情况下，我们将有 |V|/2 条路径，所以时间复杂度可以是 O(n^2)。
我想听听一些改进任务的建议。
非常感谢！
只能有两种类型的路径 - 通过 k 的路径和不通过 k 的路径：
s --> ... --> vs --> ... --> k --> ... --> v
现在要找到第一类路径，我们可以简单地从具有特殊条件的节点 s 进行 BFS - 如果我们碰巧到达节点 k[=20=，我们就不能去任何地方]
对于其他路径，我们可以将它们分成两部分，s --> ... --> k 和 k --> v，注意第一部分已经为第一个 BFS 所知。现在我们可以再次进行 BFS，这次是从节点 k.
现在任何 v 的最短路径 s --> v 只是 min(type1PathCost[v], type1PathCost[k] + type2PathCost[v] * 5)