设\(dist[x]\)表示源点到\(x\)的最短路的距离（图中无负环），若对图中任意一条边\((x,y,z)\)满足\(dist[y]≤dist[x]+z\)，那么\(dist\)就是最短路数组
证：考虑任意一个点\(a\)，假设找出了一条源点到\(a\)的最短路径{\(x_0,x_1,...,x_n,a\)}，那么显然这条路径上\(x_0\)到任意一个点一定是最短路径；我们来证明对任意一个\(x_i\)有\(dist[x_i]\)为最短路径
对\(x_1\)来说，有\(dist[x_1]≤dist[x_0]+z_{x_0->x_1}=z_{x_0->x_1}\)，由于\(z_{x_0->x_1}\)是最短的，所以\(dist[x_1]=z_{x_0->x_1}\)，所以\(x_1\)满足
对\(x_i\)来说，若前面的点都满足\(dist\)为最短路数组，那么有\(dist[x_i]≤dist[x_{i-1}]+z_{x_{i-1}->x_i}\)；由于\(dist[x_{i-1}]+z_{x_{i-1}->x_i}\)表示的是最短路，所以\(dist[x_i]=dist[x_{i-1}]+z_{x_{i-1}->x_i}\)，得证
标签：源点,dist,短路,路径,证明,bellmax,ford,任意 From： https://www.cnblogs.com/dingxingdi/p/18200470