从给定的最短路径中找到对应的图

Question

给定 n 个点和这些点之间的距离 d，我需要找到相应的无向加权图来得出这些距离。我尝试使用 Prim 的算法来查找 MST，但是这个集合的大小为 n-1，并且不包括 n 个所需的边。例如。由 n 个距离给出 n

0 3 5
3 0 4
5 4 0

我需要找到对应的边：

1 - 2 = 3
1 - 3 = 5
2 - 3 = 4

图表中的结果：

      3
1 --------- 2
 \         /
        /4
   \     /
    \   /
      3

但是 Prim 会 return 只有前 2 个边，因为 MST 不包含任何循环。

Answer 1

会导致这些距离的一个图是从每个节点到每个其他节点都有一条边的图，并且该边的长度是根据矩阵的距离。（我不确定你所说的未加权定向是什么意思，因为你给出的例子似乎是无向的，我不确定这里的权重和长度之间有什么区别）。

另一种选择是按递增顺序考虑距离，就像您对 Prim 算法所做的那样，并且除了检查边是否需要连接其两端外，还要检查最小值是否到目前为止重建的图中这些端点之间的距离与矩阵中的距离相同。如果不是，即使到目前为止图中的端点已连接，也添加边。

Finding corresponding graph from given shortest paths