星星和月亮 发表于 2009-5-25 12:57

根据矩阵怎样求任意两点间最短距离的数量

本帖最后由 星星和月亮 于 2009-5-25 14:01 编辑

用矩阵表示一个图形，矩阵中为1的部分表示该两点间有连接，怎样根据矩阵来求任意两点间的最短距离的数量啊？ 例如矩阵为

0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0

表示的图形为


求任意两点间的最短距离的数量。

例如点1到2的距离就为1，点1到3的话就有好几种可能，可以经过2到3，距离为2；经过4到3，距离也为2；或者经过4，5再到3，距离为3。对1到3来说，最短距离的数量就有2个。

谢谢了。{:4_276:}

blurryblue 发表于 2009-5-25 13:07

本帖最后由 blurryblue 于 2009-5-25 14:12 编辑

这个问题被Dijkstra's algorithm解决

如果任意相连两点距离相同（为1），DFS也可以解决

matlab里。。俺不会

星星和月亮 发表于 2009-5-25 13:17

谢谢楼上哒~~~~~~~~~~~~ 关于两点间的最短距离我已经求出来了，但是最短距离的数量我就想了半天~~~~~~~~~~~~ {:4_292:} 继续等待~~~~~~~~~~~~~

星星和月亮 发表于 2009-5-26 20:58

{:4_303:}

龙欣欣 发表于 2009-5-26 23:42

http://gigapedia.info/1/algorithms%20%20shortest%20paths%20matrix

咪姆 发表于 2009-5-27 00:02

本帖最后由 咪姆 于 2009-5-27 01:17 编辑

星星我GG说 让嫩看看matlab有个自带的统计的工具箱。。。。，但是具体用哪个函数，他也不知道{:4_288:}

星星和月亮 发表于 2009-5-27 00:05

星星我GG说 让嫩看看matlab有个自带的统计的工具箱。。。。，但是具体用哪个函数，他也知道{:4_288:}
咪姆 发表于 2009-5-27 01:02 http://www.dolc.de/forum/images/common/back.gif


亲耐滴，偶用了个蛮复杂滴方法编出来鸟，但是还没调试。明天偶试试嫩GG说滴那个统计的工具箱，谢谢啦~~~~~~~~~~~~~~~~~~ {:4_301:}

咪姆 发表于 2009-5-27 00:16

{:4_299:}能算出来就好啊
他说如果就是按照你图片给的就几个点还好能用递归法，但是如果用很多就不行了，那办法太麻烦了
PS 我不知道，欧说明白了没有{:4_288:}

星星和月亮 发表于 2009-5-30 02:14

亲耐滴，那个偶算出来鸟~~~~~~~~~~~~~~~~ 用递归滴办法8行，因为偶做滴是网络模拟，要有成千上万个点和连接哒~~~~~~~~~~~~~~· 替偶谢谢嫩家GG啦~~~~~~~~~~~~~~ {:4_301:}

星星和月亮 发表于 2009-5-30 02:14

http://gigapedia.info/1/algorithms%20%20shortest%20paths%20matrix
龙欣欣 发表于 2009-5-27 00:42 http://www.dolc.de/forum/images/common/back.gif


谢谢MM啦~~~~~~~~~~~~~ {:4_295:}
页: [1] 2
查看完整版本: 根据矩阵怎样求任意两点间最短距离的数量