使用Dijkstra的找到一个最小生成树？

Question

迪杰斯特拉的通常用于找到在图形的两个节点之间的最短距离。是否可以用来寻找最小生成树？如果是的话，如何？

编辑：这不是功课，但我想了解在一个旧练习考试问题

Answer 1

严格，答案是否定的。 Dijkstra算法找出图形上的2个顶点之间的最短路径。然而，非常小的变化的算法产生另一算法并有效地产生一个MST。

的算法设计手册是我找到答案的最好的书类似这样的问题之一。

Answer 2

答案是否定的。要知道为什么，让我们先明确的问题，像这样：

Q：对于一个连接的，无向，加权图仅具有非负边权G = (V, E, w)，并通过Dijkstra算法产生的前身子图形成G的最小生成树

？

（注意，无向图是一类特殊的有向图的，所以它是完全确定使用Dijkstra的算法的无向图。另外，MST的仅限定为连接，无向图，并且是微不足道的，如果图不是加权，所以我们必须限制我们询问这些图。）

A：<强> 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作为源顶点。

Dijkstra的算法需要的边缘{ (a,b), (a,c), (a,d) }。结果 因此，该生成树的总重量是的 5 + 5 + 5 = 15

Prim算法需要边缘{ (a,d), (b,d), (c,d) }。结果 因此，该生成树的总重量是的 5 + 1 + 1 = 7

Answer 3

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

Answer 4

我会保持至贪婪算法如普里姆的或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节的基础进一步的解释。

希望这有助于