如果这个更简单、更快的算法有效，为什么我们需要 Dijkstra 算法？

Question

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

任何反馈将不胜感激。我喜欢算法:)。

Answer 1

你的算法不是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 复杂度较低