加权有向图最短路径的最佳方法

Question

关于我正在做的一个问题，我很困惑为什么答案将是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

答案是使用改进的BFS的O（n + m）时间，

我知道在将BFS与DFS进行比较时，BFS对于较短的路径更好。我也知道Dijkstra的算法与BFS相似，并且如果我没有记错的话，Dijkstra的算法更适合像这种情况下的加权图。我假设BFS更好，因为它表示已修改BFS，但是修改后的含义恰好意味着BFS会更好。

Answer 1

由于所有路径都被限制为1或2的距离，对于从节点a到b的长度为2的每个边，您都可以创建一个新节点c，其边从a到[长度为1的C0]和从c到长度为1的c的边，然后它变成只有权重为1的边的图，通常可以b来找到从BFS到最短路径的权重u。由于仅添加v个新节点和O(m)个新边，因此保留了BFS的时间复杂度O(m)。

另一种可能性是，在BFS的每个层上，存储由当前层的权重为2的边获得的节点的另一个列表，并与稍后到达两层的节点同时考虑。不过，这种方法有些挑剔。