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

Question

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

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

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

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

Answer 1

由于边权重（在本例中为距离）为正，您可以使用 Dijkstra 算法：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。

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

Answer 2

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

所以...

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

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

X和Y之间的现有网络中是否存在与其距离相等的路径？如果是这样，则不需要 link（它可能代表真实的 link，也可能不是，无论哪种方式你都不需要它）。
是不是X和Y之间现有网络中的最短路径，好吧把它加到网络中，这里一定有你没见过的真实-link。
是否 > X 和 Y 之间现有网络中的最短路径 - 错误 - 这不是这两个节点之间的最短距离，因此原始距离矩阵是错误的。

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

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

Answer 3

您可以构建最小距离矩阵（另一个包含所有最小距离的矩阵，直到单元格 [i,j]），然后 return 最后一个单元格。构建它只需要 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;
}

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

How to determine the path between 2 nodes, given the shortest distance matrix between the nodes?

algorithm

graph

graph-traversal

graph-algorithm