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 回答