公司的面试题关于floyd最短路径中的前趋矩阵的计算
回来发现是算法导论中的25.1-6
就是知道一个最短路径矩阵，怎么求前趋矩阵
假设前趋矩阵用W表示，那么W（i,j)表示的就是从I到J节点的路上的靠近J的最后一个节点的编号。
假设有向图连接矩阵是（×是不链接的意思）
0，3，8，×，-4
×，0，×，1，7
×，4，0，×，×
2，×，-5，0，×
×，×，×，6，0
算出的最短路径矩阵是
0，1，-3，2，-4，
3，0，-4，1，-1，
7，4，0，5，3，
2，-1，-5，0，-2，
8，5，1，6，0
输入最短路径矩阵得到前趋矩阵
不能用在FLOYD算法生成最短路径中，顺便生成前趋矩阵。
当时没想到好办法。。。谁能教教我。。谢谢
[解决办法]
不知道“前趋矩阵”是怎样定义的？
a[i][j]表示什么？
=1 表示j能做i的前趋？=0不能？
这样的矩阵上看不出最短路径
[解决办法]
好像很简单吗,个人觉得。
设定：w --- 前去矩阵
a --- 原始矩阵
s --- 最短路经
比如：求w[i,j]的前驱为k，则s[i,k] + s[k,j] = w[i,j]
-: 如果s[i,j] == a[i,j]则w[i,j] = a[i]
-: 循环计算，s[i,k] + s[k,j] =？s[i,j], k 从0变化到n就可以了,在
计算是参考a[i,j],如果a[i,j] = ‘X’ 则跳过。
具体计算过程是典型的动态规划过程，可以保存中间计算结果以节省时间
（完）
