使用Dijkstra找到最小生成树？
Nic*_*ner 13 language-agnostic algorithm graph-theory dijkstra minimum-spanning-tree
Dijkstra通常用于查找图中两个节点之间的最短距离.它可以用来找到最小生成树吗？如果是这样,怎么样？
编辑:这不是作业,但我试图理解旧练习考试的问题.
小智 27
答案是不.为了解原因,让我们首先阐述这样的问题:
问:对于G = (V, E, w)只有非负边权重的连通,无向加权图,Dijkstra算法产生的前任子图是否形成G的最小生成树？
(请注意,无向图是一类特殊的有向图,因此在无向图上使用Dijkstra算法是完全可以的.此外,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.
- 这是一个出色的反例。来自“ d”顶点的Dijkstra仍会产生MST。 (2认同)
- 这一定是我在 Stack Overflow 上看到的更好的答案之一！用简单的例子清楚地解释一个复杂的问题。 (2认同)