algorithm - 给定节点之间的最短距离矩阵，如何确定 2 个节点之间的路径？

Question

给定图的节点之间的最短距离矩阵，如何确定 2 个节点之间的最短路径？

比如我有4个节点和最短距离矩阵(m)。

0 4 5 8
4 0 6 3
5 6 0 2
8 3 2 0

m(i,j) 是节点 i 和节点 j 之间路径的距离，它不需要是节点 i 和节点 j 之间的边。

有人可以指导如何做到这一点吗？提前谢谢你。

Answer 1

注意:原始网络中的实际链接都出现在这个距离矩阵中，除非这两个节点之间通过另一个节点的路径更短。如果有更短的路径，那么为了解决这个问题，可以忽略这个更长距离的链接。

所以...

我将从最短距离开始。这必须表示两个节点之间的实际路径。创建一个仅包含这两个节点和它们之间的链接的图表。

现在取节点 X 和 Y 之间的下一个最短距离。

• X 和 Y 之间的现有网络中是否存在与其距离相等的路径？如果是这样，则不需要该链接(它可能代表一个真实的链接，也可能不是，无论哪种方式您都不需要它)。
• 它是 < X 和 Y 之间现有网络中的最短路径，很好地将它添加到网络中，这里必须有一个你还没有看到的真实链接。
• 它是否 > X 和 Y 之间现有网络中的最短路径 - 错误 - 它不是这两个节点之间的最短距离，因此原始距离矩阵是错误的。

继续前进，直到完成所有距离。

您现在有一个可能的网络，它是原始网络的子网络，它包含计算任何一对节点之间的每条最短路径所需的链接。现在您可以使用标准的最短路径算法计算最短路径。