data-structures - 我们需要最短路径树的任何现实问题？

Question

我可以看到我们可以在电话、电气、液压、电视电缆、计算机、道路等网络设计中使用最小生成树。不会有帮助。

Answer 1

如 this website 中所述，您将使用 MST 来“选择一组边，以便每个节点之间有一条路径。边长度的总和将被最小化”。并且您将使用 SPT 来“找到连接所有节点的边的集合，使得从根到每个节点的边长度总和最小化”。
基本上 MST 关注所有节点之间的最短路径，而 SPT 关注从根到每个节点的最短路径。
在实际示例中，SPT 用于地理 map 、电话网络，并且通常用于 IP 路由算法(基本上是当您需要从根以最小长度到达每个节点时)。
这是使用实际图形的示例:


如您所见，MST 查找连接所有节点的最小权重，而 SPT 查找从特定节点开始时的最小权重。
在实际示例中，您将使用 SPT 而不是 MST 用于医院及其所在地区的家庭。目标是找到从医院到每个家庭的最短路径。这样，在紧急情况下，救护车可以从医院出发，以尽可能小的距离到达任何家。