如何由邻接矩阵求出距离矩阵

来源：百度知道 编辑：UC知道 时间：2024/06/18 14:39:28
在图论中，已知图的邻接矩阵，如何求出他的距离矩阵？最好能有编程实现的算法。

最简单是用Floyd法,即是用动态规划做道路松弛. 先将道路邻接矩阵填入d(i,j).
过程:枚举i,j,k:d(i,j)=min{d(i,k)+d(k,j)}
最后得到的d(i,j)就是距离.

设邻接矩阵表示的图有i个节点，那么求距离矩阵就是求从某节点出发，到另外(i-1)个节点的最短路径。

距离矩阵的对角线必定为0，并且关于对角线对称。

就是说只要做i(i-1)/2次最短路径就可以了。