如何确定两个节点之间的路径，已知节点之间的最短距离矩阵？

Question

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

例如，假设有4个节点和最短距离矩阵(m)。

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

m(i,j)是节点i和节点j之间路径的距离，它们之间不一定有边相连。

有人能指导如何实现吗？提前感谢您。

- aries

---

我猜问题应该是这样表述的：如何确定最短路径...。 - guido

好的，已经更正了。 - aries

我不确定您所提供的矩阵是否正确。如果2/4之间的最短距离为3，4/3之间的距离为2，那么2/3之间的最短距离怎么可能是6呢？使用路径2-4-3，代价应该是5。如果我错了，请纠正我。 - vish4071

Answer 1

注意：除非通过另一个节点有更短的路径，否则原始网络中实际链接都包含在此距离矩阵中。如果存在更短的路径，则可以忽略较长的距离链接以解决此问题。

所以...

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

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

- 存在现有网络中X和Y之间等距离的路径吗？如果是，则不需要该链接（它可能表示实际链接，也可能不是，无论如何您都不需要它）。 - 它是否小于现有网络中X和Y之间的最短路径？如果是，请将其添加到网络中，必须有一个尚未看到的实际链接。 - 它是否大于现有网络中X和Y之间的最短路径 - 错误 - 它不是这两个节点之间的最短距离，因此原始距离矩阵是错误的。

继续进行，直到使用所有距离为止。

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

- Ian Mercer

---

好的，如果我成功实现了，我会发布它。谢谢。 - aries

第三个条件（它是否大于现有网络中的最短路径）总是成立的，不是吗？因为下一个最短距离总是大于初始距离。也许我理解错了，您能否请澄清一下？ - aries

这应该始终为false，否则你开始使用的距离矩阵是错误的：如果距离矩阵表示两个节点之间的最短路径是X，但你已经找到了一个更短的路径Y，那么制作原始矩阵的人就犯了一个错误。我会澄清一下。 - Ian Mercer

它运行良好 :) 谢谢。我还找到了另一种解决方案。这个想法是使用Kruskal算法获取最小生成树，然后使用DFS获取两点之间的路径。 - aries

Answer 2

由于边的权重（在这种情况下是距离）是正数，您可以使用Dijkstra算法：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。

C语言实现：http://www.ccodechamp.com/c-program-to-find-shortest-path-using-dijkstras-algorithm/。

- user3235832

---

假设网络是 A--2-->B--2-->C。在距离矩阵中，A 到 C 的距离为 4，但它们之间没有连接。Dijkstra 算法可能会认为这是一条路径，但实际上不是，因为在到达距离 4 时可以采取任何一步。原帖中有一个最短距离矩阵而不是边缘矩阵，它包含可能不存在于现实世界中的链接，因为它们是通过其他节点进行的。 - Ian Mercer

Answer 3

您可以构建最小距离矩阵（另一个包含所有最小距离直到单元格[i，j]的矩阵），然后返回最后一个单元格。仅构建此矩阵需要O(n)。n是矩阵中项目的数量。

这里是构建最小距离矩阵的C#实现。

public static int[,] mindi_loop(int[,] original_mat)
{
    int[,] mindi_mat = new int[original_mat.GetLength(0), original_mat.GetLength(1)];
    for (int i = 0; i < original_mat.GetLength(0); i++)
    {
        for (int j = 0; j < original_mat.GetLength(1); j++)
        {
            if (i > 0 && j > 0)
            {
                mindi_mat[i, j] = Math.Min(mindi_mat[i - 1, j], mindi_mat[i, j - 1]) + original_mat[i, j];         
            }
            else if (i > 0 && j < 1)
            {
                mindi_mat[i, j] = mindi_mat[i - 1, j] + original_mat[i, j];
            }
            else if (j > 0 && i < 1)
            {
                mindi_mat[i, j] = mindi_mat[i, j - 1] + original_mat[i, j];
            }
            else if (i==0 && j == 0)
            {
                mindi_mat[i, j] = original_mat[i, j];
            }
        }
    }
    return mindi_mat;
}   

- aerin