c++ - 使用 Dijkstra 算法的最小生成树

Question

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

我为此做了一些表格并标记了那棵树的最佳路径。

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

Answer 1

Dijkstra 不能用于查找图的 MST。这是一种寻找节点之间最短路径的贪心算法。因此，虽然它最大限度地减少了从一个节点到其他节点的成本，但它并不总是为整个图生成 MST。 Dijkstra 边的总权重可能不等于 MST 的总权重。