我得到了一张带有成本和字母的图表。我的任务不是找到从一个节点到另一个节点的最佳路径 - 这是找到一棵最小生成树。
我为此目的做了一些表格,并标记了该树的最佳路径。
但我不知道是否应该从 K 节点进一步到达另一个节点。尽管如此,目的不是找到从 A 到 K 的最佳路径,而是 MST。
最佳答案
Dijkstra 不能用于查找图的 MST。它是一种寻找节点之间最短路径的贪心算法。因此,虽然它最大限度地减少了从一个节点到其他节点的成本,但它并不总是会生成整个图的 MST。 Dijkstra 边的总权重可能不等于 MST 的总权重。
关于c++ - 使用 Dijkstra 算法的最小生成树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54531951/