有关弗洛伊德算法的一个疑问,该如何解决

有关弗洛伊德算法的一个疑问

C# code

Floyed(){    const int n = 100;    for (int k = 0; k < n; k++)    for (int i = 0; i < n; i++)    for (int j = 0; j < n; j++)         if (mat[i, j] > mat[i, k] + mat[k, j])            {                 mat[i, j] = mat[i, k] + mat[k, j];                 rec[i, j] = k;            }                }

想问一下，如上弗洛伊德算法中，最后的rec数组表示的是什么意思？

[解决办法]
mat记录权值，rec记录具体哪一个顶点构成了路径。
[解决办法]
从i到j的最短路径的i的下一个邻接点。
如果i--k--m--j这最短路径。
那么rec[i,j]=k

查看更多 下一篇