当前位置: 代码迷 >> 数据结构与算法 >> 公司的面试题关于floyd最短路径中的前趋矩阵的计算,该如何解决
  详细解决方案

公司的面试题关于floyd最短路径中的前趋矩阵的计算,该如何解决

热度:601   发布时间:2016-05-23 09:14:30.0
公司的面试题关于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’ 则跳过。
具体计算过程是典型的动态规划过程,可以保存中间计算结果以节省时间
(完)
  相关解决方案
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!
 
  • 最近登录:Tue Oct 24 06:40:18 CST 2017
  • 最近登录:Tue Oct 24 06:40:18 CST 2017
  • 最近登录:Tue Oct 24 06:40:18 CST 2017
  • 最近登录:Tue Oct 24 06:40:18 CST 2017
  • 最近登录:Tue Oct 24 06:40:18 CST 2017