21

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

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

4

5 回答 5

50

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

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

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

答：Dijkstra 算法在每一步都贪婪地选择最接近某个源顶点 s的下一条边。它这样做直到 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为源顶点。

图 G 的图片

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

Prim 算法占据优势{ (a,d), (b,d), (c,d) }。
因此，此生成树的总权重为5 + 1 + 1 = 7。

于 2013-12-09T22:30:39.320 回答
22

严格来说，答案是否定的。Dijkstra 算法在图上找到 2 个顶点之间的最短路径。但是，对算法进行非常小的更改会产生另一种算法，该算法确实可以有效地产生 MST。

《算法设计手册》是我找到的回答此类问题的最佳书籍。

于 2009-12-15T18:14:46.777 回答
5

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

于 2009-12-15T18:15:07.790 回答
1

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

于 2009-12-15T18:14:08.277 回答
1

当然，可以将 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 生成树的示例：

使用 Dijkstra 生成树的示例

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

希望这有帮助

于 2013-12-11T13:45:02.460 回答