floyed算法【最短路】【模板】

唯一的多源最短路算法

本质:

第一重循环每一次在图上增加【一个点和它所依附的边】,以此来更新两点间的距离

理论证明:

一个点当过中点,它就不再是所在的连通的路径上的边缘结点,即,只要是边缘结点就还没有被当作过中点,而当两条连通路径的边缘结点相同时,两条路径就会通,并且这种情况必然发生

例题:灾后重建就是这样,只要不是这两个村庄挨着,要想通过其它村庄相连,其路径上的村庄就必然都被当作过中间结点(重建好了),利用这个特点可以实时更新道路通畅情况(想象中中间路径部分点修好了,但是由于没修好的点与其相邻的点也看作了通路,所以害怕依此制造了伪通路,但实际不会,因为一个点要作为桥梁连通其它任意两个点的情况只会出现在这个点是中间点时,其他时候通过它的任意两点都无法形成通路)

【我的代码值得借鉴】

原文地址:https://www.cnblogs.com/bear-xin/p/14948856.html