algorithm - Dijkstra 算法问题

Question

如何对图应用 Dijkstra 算法以找到 MST，使得生成的树必须在两个给定顶点之间有一条边？（例如：MST 必须包含 X 和 Y 之间的边）

谢谢

Answer 1

Dijkstra 算法适用于最短路径（不是 MST），但与 Dijkstra 算法类似，经过修改以找到最小生成树，称为 Prim 算法。Prim 的算法保持一棵不断增长的树，直到它跨越整个图。此处引入的附加约束不会造成太大困难：您只需从 XY 作为您的树开始。

具体来说，假设您的 MST 必须包含边 (X,Y)（如果有多个这样的边选择权重最小的边），请从具有两个节点 X 和 Y 以及它们之间的边的树开始。现在在每一步选择最小的边 (u,v)，其中 u 在树中，v 在外面，将节点 v 和边 (u,v) 添加到树中，然后重复。