时间戳

首页 > 解决方案 > 加权有向图最短路径的最佳方法

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

问题描述

对于我正在做的一个问题，我很困惑为什么答案是 BFS 而不是 Dijkstra 的算法。

问题是：有一个加权有向图 G=(V,E) 有 n 个节点和 m 个边。每个节点的权重为 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 会更好。

标签： algorithmtime-complexitydepth-first-searchbreadth-first-searchdijkstra

解决方案

由于所有路径的距离都限制为 1 或 2，因此对于从节点a到b您的每条长度为 2 的边，您只需创建一个新节点c，其边距a为c1，边距c为b1，然后这个变成只有权重为 1 的边的图，通常可以BFS'd 找到从u到的最短路径v。由于您只添加O(m)新节点和O(m)新边，因此 BFS 的时间复杂度为O(n+m).

另一种可能性是，在 BFS 的每一层，存储另一个由当前层的权重为 2 的边获得的节点列表，并同时考虑它们作为稍后获得两层的节点。这种方法虽然有点挑剔。

推荐阅读