algorithm - 最轻的路径树

Question

我需要编写算法在有向和加权图中找到最轻的路径树。（应该尽可能高效）我得到一个顶点 S 并且需要构建一个从 S 到可以从 S 接近的所有顶点的路径树，因此树中的路径是最轻的（路径权重是没有末端的路径)

我考虑过首先计算到 S 的所有距离然后对于每条路径都会有一个新的权重：权重减去端点然后在带有新权重的图表上运行 dijkstra ...

它会起作用吗？是否足够高效？如何计算距离？

Answer 1

您的评论表明您实际上是在寻找从单一来源到所有顶点的最短路径。

看看Dijkstra 的算法是如何工作的。该算法从大小为 1 的树（仅源）开始，并迭代地将顶点添加到树中。最后，由 dijkstra 算法创建的树表示从源到图中每个节点的最短路径。

请注意，dijkstra 的算法需要边缘上的权重函数，而您的权重函数在顶点上。它可以通过定义一个新的权重函数来轻松解决w':E->R：（w'(u,v) = w(u)它可以工作，因为你不想计算结束）。

Answer 2

听起来您要的是最小生成树。维基百科页面讨论算法。