(测试代码中10松弛,此时D[v]变成10,而它的前驱节点也变成了 u)
#relaxtion
inf = float('inf')
def relax(W, u, v, D, P):...现在我们考虑一个问题,如果我们对图中的所有边都松弛一遍会怎样?可能部分顶点的距离估计值有所减小对吧,那如果再对图中的所有边都松弛一遍又会怎样呢?...那就想办法对图进行些预处理,使得所有边的权值都是正的就可以了,那怎么处理能够做到呢?此时可以看下前面的三角不等性质,内容如下:
d(s,v) 的选择还是不选择这种策略,如果我们选择不经过节点 k 的话,那么问题变成了求从起点 u 到终点 v 只能够经过编号为(1,2,3,…,k-1)的节点的最短路径问题;如果我们选择经过节点...k 的话,那么问题变成求从起点 u 到终点 k 只能够经过编号为(1,2,3,…,k-1)的节点的最短路径问题与求从起点 k 到终点 v 只能够经过编号为(1,2,3,…,k-1)的节点的最短路径问题之和