小编Rex*_*Aex的帖子

我有一个通过 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] …