对于一个我正在做的问题，我很困惑，为什么答案将是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）使用修改后的BFS的O（n + m）时间，
我知道将BFS与DFS进行比较时，BFS对于较短的路径更好。我也知道Dijkstra的算法类似于BFS，如果我没记错的话，Dijkstra的算法更适合于这种情况下的加权图。我假设BFS更好，因为它表示已修改BFS，但是修改后的含义恰好意味着BFS会更好。
由于所有路径的距离限制为1或2，因此从节点a到长度为2的每个边b都可以创建一个新节点c，其边的长度为ato c，长度为1，边的长度为cto b，长度为1。变成只有权重为1的边的图，BFS通常可以找到从u到的最短路径v。由于仅添加O(m)新节点和O(m)新边缘，因此使BFS的时间复杂度保持为O(n+m)。
另一种可能性是，在BFS的每个层上，存储由当前层的权重为2的边获得的节点的另一列表，并与稍后获得两层的节点同时考虑。不过，这种方法有些挑剔。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句