使用 Dijkstra 找到最小生成树？

Question

Dijkstra 通常用于查找图中两个节点之间的最短距离。它可以用来查找最小生成树吗？如果是这样，怎么办？

编辑：这不是作业，但我试图理解旧练习考试中的一个问题。

Answer 1

答案是否定的。要了解原因，让我们首先像这样阐明问题：

问：对于仅具有非负边权重的连通、无向、带权图 G = (V, E, w)，前驱子图是否由Dijkstra算法形成G的最小生成树？

（请注意，无向图是一类特殊的有向图，因此在无向图上使用 Dijkstra 算法是完全可以的。此外，MST 仅针对连通的无向图定义，如果图未加权，则 MST 是微不足道的，因此我们必须将我们的查询限制在这些图上。）

答：Dijkstra 算法在每一步都会贪婪地选择最接近某个源顶点的下一条边。它会执行此操作，直到 s 连接到图中的所有其他顶点。显然，生成的前驱子图是 G 的生成树，但是边权重之和是否最小化了？

Prim 算法已知可以生成最小生成树，与 Dijkstra 算法高度相似，但在每个阶段它都会贪婪地选择最接近当前工作中任何顶点的下一条边该阶段的 MST。让我们用这个观察来产生一个反例。

反例：考虑无向图G = (V, E, w)，其中

V = { a, b, c, d }

E = { (a, b), (a,c), (a,d), (b,d), (c,d) }

w = {
( (a,b) , 5 )
( (a,c) , 5 )
( (a,d) , 5 )
( (b,d) , 1 )
( (c,d) , 1 )
}

以a为源顶点。

Dijkstra 算法取边 { (a,b), (a,c), ( a,d) }.
因此，这棵生成树的总权重为5 + 5 + 5 = 15。

Prim 算法采用边{ (a,d), (b,d), (c,d) }。
因此，这棵生成树的总权重为5 + 1 + 1 = 7。

Answer 2

严格来说，答案是否定的。 Dijkstra 算法找到图上 2 个顶点之间的最短路径。然而，对算法进行很小的改变就会产生另一种能够有效生成 MST 的算法。

算法设计手册是我发现回答此类问题的最好的书一。

Answer 3

Prim 算法 使用与 Dijkstra 算法相同的基本原理。

Answer 4

我会坚持使用 Prim 或 Kruskal 等贪婪算法。我担心 Djikstra 不会这样做，只是因为它最大限度地减少了节点对之间的成本，而不是整个树的成本。

Answer 5

当然，可以使用 Dijkstra 进行最小生成树：

dijsktra(s):
dist[s] = 0;
while (some vertices are unmarked) {
    v = unmarked vertex with 
    smallest dist;
    Mark v; // v leaves “table”
    for (each w adj to v) {
        dist[w] = min[ dist[w], dist[v] + c(v,w) ];
    }
}

这是使用 Dijkstra 进行生成树的示例：

您可以在《算法基础》一书第 4 章第 2 节中找到进一步的解释。

希望这会有所帮助