algorithm - 为什么 kruskal 算法和 dijkstra 算法如此相似？

Question

我知道这两种算法用于解决不同的问题，dijkstra 算法用于在图中找到最短路径，而 kruskal 算法用于找到图的 MST。但是它们彼此如此相似吗？他们之间是什么关系？这两位作者之间的关系是什么？为什么它们如此相似？

Answer 1

它们是不同的算法。在 Kruskal 中，您选择整个图中的最短边（并将其从进一步考虑中删除）。在 Dijkstra 中，您选择具有最短暂定距离的顶点（并将其从进一步考虑中删除）。

当然，解决的问题也大相径庭。两个顶点之间的最短路径可能不是最小生成树的一部分。

一个例子是一个边长为 1 的正方形，删除任何一条边都会给你一个最小生成树，但是你删除的边的顶点之间的原始正方形图中的最短路径不是最小生成树的一部分。

---

来自评论：

好吧，Prim's 比 Kruskaln 更接近 Dijkstra。为了完整起见，Prim 总是选择迄今为止最接近树的顶点。相反，Dijkstra 可能不会选择最接近最终顶点集的顶点。例如，顺时针边长为 1、2、3、1、2、4 的六边形。 Prim 可以一直顺时针生长。Dijkstra 将双向增长。