algorithm - 加权无向树中两个节点之间的平均距离

Question

您好我正在尝试弄清楚如何计算加权无向图中两个节点之间的平均距离。此外，这个图是一棵树，所以它有 V - 1 条边。

我考虑过使用 Floyd Warshall 计算所有最短路径，然后计算平均值。但这将是 O(E^3) 时间复杂度。这真的是不够的。

我也一直在考虑使用动态编程来解决它，但我真的不明白如何......谁能给我一些建议吗？我不想要一个直接的答案，只是一些提示，以便我可以继续思考:)

Answer 1

建立并维护所有最短路径的表（不足为奇）。每个条目包括最低已知成本和路径。

通过填充所有边（仅长度为 1 的路径）开始表格；其他条目是inf.

遍历表，考虑两种情况：左侧添加节点，右侧添加节点。在每一端，只考虑从端节点通过一条边可到达的节点。该路径是否比现有条目短？

例如，假设我们在节点 I 和 J 之间有一条边；叫它IJ，我们也有edge JK。IJ + JK 的成本是否小于边缘 IK 的当前条目？如果是，替换它并记录路径IJK；如果没有，请转到下一个边缘/节点/路径。

您可以遍历所有现有路径，直到没有更新。也许更好的是，索引使用每条最短路径的路径；这允许您在改进特定子路径时更新所有路径。

继续该过程，直到您完全通过图表而没有更新。如果您维护该子路径索引，我认为您可以在图上仅通过一两次即可完成此操作。我相信这将使过程O(E*N^2)（在边缘和节点上）。