一点额外的理解
查看原帖
一点额外的理解
184271
l55584楼主2021/8/30 12:08

原式到三角形不等式的变形

如果变形为dis[i]<=dis[j]+d[j][i]的形式,求最短路,相当于对所有点的值加以多个上界约束 ;因而求出的解应当是最大的

如果变形为dis[i]>=dis[j]+d[j][i]的形式,求最长路,相当于对所有点的值加以下界约束,因而求出的解应当是最小的

那是不是说每个值的值域都能算出来?

2021/8/30 12:08
加载中...