如何由邻接矩阵求出距离矩阵
来源:百度知道 编辑:UC知道 时间:2024/08/31 17:20:29
在图论中,已知图的邻接矩阵,如何求出他的距离矩阵?最好能有编程实现的算法。
最简单是用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次最短路径就可以了。