使用Dijkstra算法的最小生成树

Question

我得到了一张有成本和字母的图表。我的任务不是找到从一个节点到另一个节点的最佳路径 - 这是找到最小生成树。

我为此目的做了一些表，并标记了该树的最佳路径。

但我不知道我是否应该从K节点进一步到另一个节点。尽管如此，目的并不是找到从A到K的最佳路径，而是MST。

Answer 1

Dijkstra不能用于查找图形的MST。它是一种贪心算法，可以找到节点之间的最短路径。因此，虽然它最大限度地降低了从一个节点到另一个节点的成本，但它并不总能为整个图形生成MST。 Dijkstra的边缘总重量可能不等于MST的总重量。

Answer 2

Dijkstra的算法本身不会准确地找到图的最小生成树。它旨在找到从源顶点到图中每个其他顶点的最短路径。因此，在每一步，Dijkstra的算法都会贪婪地选择最接近源顶点的下一条边。它一直持续到源顶点连接到图中的每个其他顶点。因此，沿着每个步骤，生成的当前图形是前一图形的生成树，但是边缘权重的总和不是最小化的，因为它仅考虑与源顶点相关的顶点。

然而，用于产生最小生成树的Prim算法在程序上与Dijkstra算法非常相似。但是，在每一步中，它不是选择最接近当前顶点的下一条边，而是贪婪地选择最接近当前最小生成树（它正在生成的图形）中任何顶点的下一条边。

Answer 3

使用boost::graph库。请参阅目录here。特别是它包含算法Kruskal minimum spannig tree和Prim minimum spannig tree。

---