最短路径的加权有向图最佳方法
Weighted Directed Graph best method for shortest path
对于我正在做的一个问题，我很困惑为什么答案是 BFS 而不是 Dijkstra 算法。
问题是：有一个有 n 个节点和 m 个边的加权有向图 G=(V,E)。每个节点的权重为 1 或 2。问题是找出使用哪种算法来找到 G 中从给定顶点 u 到给定顶点 v 的最短路径。选项为：
a) O(n+m) time using a modified BFS
b) O(n+m) time using a modified DFS
c) O(mlogn) time using Dijkstra's Algorithm
d) O(n^3) time using modified Floyd-Warshall algorithm
答案是 a) O(n+m) 次使用修改后的 BFS，
我知道在比较 BFS 和 DFS 时，BFS 更适合较短的路径。我也知道 Dijkstra 的算法类似于 BFS，如果我没记错的话，Dijkstra 的算法更适合像本例中那样的加权图。我假设 BFS 更好，因为它说修改后的 BFS 但修改的确切含义是什么，或者还有其他原因 BFS 会更好。
由于所有路径的距离都被限制为 1 或 2，对于从节点 a 到 b 的每条长度为 2 的边，您只需创建一个新节点 c从 a 到 c 的边长度为 1，从 c 到 b 的边长度为 1，然后这就变成了一个只有权重为 1 的边的图可以 BFS 通常找到从 u 到 v 的最短路径。由于您只添加 O(m) 个新节点和 O(m) 个新边，因此 BFS 的时间复杂度保持在 O(n+m).
另一种可能是，在BFS的每一层，存储另一份权重为2的边从当前层到达的节点列表，并将它们与后两层到达的节点同时考虑。不过这种方法有点挑剔。
对于我正在做的一个问题，我很困惑为什么答案是 BFS 而不是 Dijkstra 算法。
问题是：有一个有 n 个节点和 m 个边的加权有向图 G=(V,E)。每个节点的权重为 1 或 2。问题是找出使用哪种算法来找到 G 中从给定顶点 u 到给定顶点 v 的最短路径。选项为：
a) O(n+m) time using a modified BFS
b) O(n+m) time using a modified DFS
c) O(mlogn) time using Dijkstra's Algorithm
d) O(n^3) time using modified Floyd-Warshall algorithm
答案是 a) O(n+m) 次使用修改后的 BFS，
我知道在比较 BFS 和 DFS 时，BFS 更适合较短的路径。我也知道 Dijkstra 的算法类似于 BFS，如果我没记错的话，Dijkstra 的算法更适合像本例中那样的加权图。我假设 BFS 更好，因为它说修改后的 BFS 但修改的确切含义是什么，或者还有其他原因 BFS 会更好。
由于所有路径的距离都被限制为 1 或 2，对于从节点 a 到 b 的每条长度为 2 的边，您只需创建一个新节点 c从 a 到 c 的边长度为 1，从 c 到 b 的边长度为 1，然后这就变成了一个只有权重为 1 的边的图可以 BFS 通常找到从 u 到 v 的最短路径。由于您只添加 O(m) 个新节点和 O(m) 个新边，因此 BFS 的时间复杂度保持在 O(n+m).
另一种可能是，在BFS的每一层，存储另一份权重为2的边从当前层到达的节点列表，并将它们与后两层到达的节点同时考虑。不过这种方法有点挑剔。