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

Why do we need Dijkstra's algorithm if this simpler, faster algorithm works?

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

如有任何反馈,我们将不胜感激。我喜欢算法 :).

在未加权的图中,BFS 确实是获取距离的正确工具。但是,在边长不同的加权图中,它会失败。为自己构建一个图,其中有两条从节点 s 到节点 t 的路径:一条路径具有少量节点和粗边,另一条(较短)具有许多节点和轻边。看看你的算法做了什么。

考虑这张图:

 A --- 5 --> B --- 1 --> C --- 1 ---> D
 |           ^
 |           |
  
 1           1

 |           |
 v           |
 E --- 1 --> F

通过 A -> E -> F -> B -> C -> D 找到从 A 到 D 的最短路径,总距离为 5。但是,您的算法不能保证找到它。想象一下发生以下情况:

首先,我们处理节点A。这将分别标记到B和E的距离为5和1,并将B入队,然后是E。现在队列是[B,E]。

接下来,我们处理节点B。这将到C的距离标记为6(B在距离5处,加上距离边缘的1),然后将C入队到队列中。队列现在是 [E, C]。

接下来,我们处理节点 E。这将到 F 的距离标记为 2(E 距离为 1,加上边缘的 1),然后将 F 入队。队列现在是 [C, F]。

接下来,我们处理节点 C。这将到 D 的距离标记为 7(C 的距离为 6,加上距边缘的 1),然后将 D 入队。队列现在为 [F, D]。

接下来,我们处理节点 F。这将到 B 的距离标记为 3(F 的距离为 2,加上距边缘的 1),然后将 B 入队。队列现在为 [D, B]。

接下来,我们处理节点D。这没有任何效果。队列现在是 [B].

接下来,我们处理节点 B。这会将节点 C 的距离更改为 4(B 的距离为 3,加上距边缘的 1)。但是,队列没有更新,因为 B 已经被处理过。

至此,我们完成了。但是请注意到 D 的距离是错误的——我们将 D 设置为距离七,但实际距离是五。为什么是这样?这是因为当我们沿着距离 3 的路径 A -> E -> F -> B 重新访问 B 时,我们已经假设它的距离为 5 来处理 B,现在我们已经意识到到 B 的距离更短,我们没有机会再次沿着 B 的所有路径查看会发生什么。我们确实更新了与其紧邻的 C,但不更新与 B 不相邻的 D。

Dijkstra 的算法避免了这种情况,方法是在完成从 A -> E -> F -> B 的路径查看并意识到对 C 的原始猜测不正确之前不扩展 C。这就是为什么按估计成本的顺序而不是按常规 breadth-first 顺序处理节点很重要。

你的算法不是O(|V|+|E|).

考虑一个完全连接的图 G(V,E),其中每个节点都与其他所有节点连接。

在你的算法中,你将这样一个图的每个节点添加到队列 |V-1| 次,startnode 被添加到队列 |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-complexity