python - Dijkstra 的算法只是 BFS，您还计算节点权重吗？

Question

对于在线类(class)，我的任务是实现 Dijkstra 算法。我完成了所描述的算法，您在其中维护已探索和未探索节点的列表，并在遍历图形(并将节点移动到已探索列表)时更新其未探索邻居的距离分数。

我注意到这看起来很像面包优先搜索，所以我尝试修改 BFS 以在节点添加到队列时更新节点分数。这似乎工作完全相同，但没有明确跟踪探索队列和未探索队列中的节点。

这只是实现细节的问题吗？这些是 Dijkstra 算法的两个示例还是一个不同的示例？

Dijkstra 例子:

def dijkstra(graph, source):
    explored_set = set()
    all_nodes = set(graph.keys())
    node_distances = create_distance_dict(graph)
    node_distances[source] = 0
    while explored_set != all_nodes:
        current_node = min_distance(node_distances, explored_set)
        explored_set.add(current_node)
        update_distances(graph, node_distances, current_node)
    return node_distances

def min_distance(distances_dict, explored_set):
    """ Helper function returns lowest distance node not yet explored """
    minimum = float("infinity")
    for node in distances_dict.keys():
        if node not in explored_set and distances_dict[node] <= minimum:
            minimum, min_index = distances_dict[node], node
    return min_index


def update_distances(graph, distances_dict, current_node):
    """ Helper function updates neighbor's distances """
    for n in graph[current_node]:
        if distances_dict[n[0]] > distances_dict[current_node] + n[1]:
            distances_dict[n[0]] = distances_dict[current_node] + n[1]

基于 bfs 的搜索示例

def search(graph, source, nodeDistances):
    nodeDistances[source] = 0
    queue = deque([source])
    while len(queue) != 0:
        n = queue.popleft()
        for m in graph[n]:
        # Iterate each node connected to n
            if m and nodeDistances[m[0]] > nodeDistances[n] + m[1] :
            # Compare current m score and update if n + n-m edge is shorter
                nodeDistances[m[0]] = nodeDistances[n] + m[1]
                # add m to search queue
                queue.extend([m[0]])

    return nodeDistances

用于两个示例的图形和节点距离结构:

nodeDistances = {
    1: 0,
    2: float("infinity"),
    3: float("infinity"),
    4: float("infinity"),
    5: float("infinity"),
    6: float("infinity"),
    7: float("infinity"),
    8: float("infinity"),
    }
graph = {
    1: [(2,1),(8,2)],
    2: [(1,1),(3,1)],
    3: [(2,1),(4,1)],
    4: [(3,1),(5,1)],
    5: [(4,1),(6,1)],
    6: [(5,1),(7,1)],
    7: [(6,1),(8,1)],
    8: [(7,1),(1,2)],
}

Answer 1

简短的回答是:不，Dijkstra 算法不是广度优先搜索。

如本 Stack Overflow 帖子中所述:Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster? ,

Dijkstra 算法分析图的加权边，同时 BFS 分析最短距离一次一步。

以下图为例(未按比例绘制):

        10
  A --------- B 
5  \          |
    C -- D    |
       3  \   | 10
           \  |
         8  \ |
             E

在上面，BFS 会发现从 A 到 E 的最短路径是 A -> B -> E，这对于 步数。 然而，Dijkstra 算法会发现从 A 到 E 的最短路径是 A -> C -> D -> E，因为 边的权重图表的。

BFS 从 A 到 E 的距离是 20 个单位，而通过 Dijkstra 算法从 A 到 E 的最短距离是 16。