我有一个通过 BFS 迭代整个图的算法,它会更新分数以找到所有节点的最小值。而且我相信它的运行时复杂度是 O(V+E),我认为它比 Dijkstra 更好。现在显然我还没有天真到真的认为这个算法是正确的。但是,我很好奇在哪种情况下,这不会找到最佳的最小路径。这是我的代码
from queue import Queue
ad_list = {
'A': {'B': 1, 'D': 3},
'B': {'A': 1, 'D': 1, 'C': 5},
'D': {'A': 3, 'B': 1, 'C': 3},
'C': {'B': 5, 'D': 3}
}
min_weights = {
'A': 0,
'B': float('inf'),
'C': float('inf'),
'D': float('inf'),
}
def fake_dijkstra(ad_list):
queue = Queue()
queue.put('A')
visited = {}
global min_weights
while not queue.empty():
key = queue.get()
# update score
children = ad_list[key]
for child_key, value in children.items():
if min_weights[child_key] > min_weights[key] + value:
min_weights[child_key] = min_weights[key] + value
if key in visited:
continue
visited[key] = True
children = ad_list[key]
for child_key, value in children.items():
queue.put(child_key)
fake_dijkstra(ad_list)
print(min_weights)
# for this case, it correctly finds the min weight to all nodes
{'A': 0, 'B': 1, 'C': 5, 'D': 2}
如有任何反馈,我们将不胜感激。我喜欢算法 :)。
最佳答案
您的算法不是O(|V|+|E|)。
考虑一个完全连接的图 G(V,E),其中每个节点都与其他所有节点连接。
在你的算法中,你将这样一个图的每个节点添加到队列 |V-1| 次,起始节点被添加到队列 |V|次。因此,队列中元素的总数是 |V| x |V-1| + 1
对于队列中的每个元素,您将遍历其所有 |V-1| 子元素以检查最小权重。
因此总步数是|V| x |V-1| x |V-1| 这当然是 O(|V|³)
根据队列使用的数据结构,Dijkstra 算法的范围从 O(|V|² + |E|) 到 O(|V| x log |V| + |E|)。对于完全连接的图 |E| = |V|²,因此 Dijkstras 算法是 O(|V|²)
看来您的算法可以找到给定图的最短路径(我不是 100% 确定,但找不到反例)。但这不是典型的 BFS,因为您要多次重新评估节点的子节点。这也是与 Dijkstra 算法的不同之处。因为此时,对节点 X 的子节点进行评估(即从 X -> Y 采取步骤),可以保证从 A 到 X 没有更短的路径。因此,它处于较低的 O -复杂性
https://stackoverflow.com/questions/64636110/