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

星星和月亮 · 发表于 2009-5-25 13: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个。

谢谢了。

blurryblue · 发表于 2009-5-25 14:07

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

这个问题被Dijkstra's algorithm解决

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

matlab里。。俺不会

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

谢谢楼上哒~~~~~~~~~~~~ 关于两点间的最短距离我已经求出来了，但是最短距离的数量我就想了半天~~~~~~~~~~~~

继续等待~~~~~~~~~~~~~

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

龙欣欣 · 发表于 2009-5-27 00:42

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

咪姆 · 发表于 2009-5-27 01:02

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

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

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

星星我GG说让嫩看看matlab有个自带的统计的工具箱。。。。，但是具体用哪个函数，他也知道
咪姆发表于 2009-5-27 01:02

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

咪姆 · 发表于 2009-5-27 01:16

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

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

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

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

http://gigapedia.info/1/algorithms%20%20shortest%20paths%20matrix
龙欣欣发表于 2009-5-27 00:42

谢谢MM啦~~~~~~~~~~~~~

账号		自动登录	找回密码
密码			注册

萍聚头条

[其他学科] 根据矩阵怎样求任意两点间最短距离的数量

本帖子中包含更多资源