【算法分析】弗洛伊德

建议电脑端观看

算法名称       ：弗洛伊德

算法适用范围：解决图论中的多源最短路径问题

        概述：有无向图P，求任意两点之间的最短路

算法局限性   ：无

算法涉及思想：暴力，枚举

算法优越性    ：相对暴力（深搜）

        暴力做法：

                遍历每个点，以遍历到的点为起点

                对整个图进行一次深搜，得到答案

        弗洛伊德：

                遍历每个点，以遍历到的点为中间点，

                枚举两侧的起点和终点，对两条边进行松弛操作

                减少了中间点被重复计算的情况 

算法优越解释：

        命题1：有链A->N1->N2->...->Nn->B

                该链是A到B的最短路

                该链的任意松弛顺序不影响结果 

        证明1：

                知：

                        假定有一点Nan是链上的点

                        则有链N(an-1)->Nan->N(an+1)

                        该链长度为N(an-1)->Nan + Nan->N(an+1) 

                故：

                        对于整个链

                        链长为A->N1 + N1->N2 + N2->N3 + ..... + Nn->B 

                        每次选取点即在上式中任意挑选相邻两项相加 

                        由加法结合律知：总值不变

                命题1 得证 

        由命题1知：

                如下的操作可求出正确答案：

                        对任意两点Ai到Bi的最短路

                        枚举每一个点，将其任意两个直连点进行松弛

                        则必然包括最短路链上的点，和以该点为中间点的两个链上直连点

                        多次之后

                        即可求出任意两点之间的最短路

        核心优化分析：

                对上述操作，任意一个仅含有三个点的链，都只被枚举了一次

                大大减小了时间复杂度（虽然还是很大）