【算法分析】迪杰斯特拉

建议电脑端观看

算法名称       ：迪杰斯特拉

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

        概述：有无向图P，起点A，求其它P中所有点到A点得最短路长度 

算法局限性    ：负边权无法使用 

算法涉及思想：贪心，减治 

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

        暴力做法：

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

        迪杰斯特拉：

                利用有效信息进行贪心，可以减少多余的前置运算

算法优越解释：

        对初始情况，除初始点未知任何最短路径 

                设初始点为A

                图中存在一点B是A的直连点

                命题1：

                        假设A->B的长度小于其它A的直连点到A的长度

                        则A->B是A到B的最短路 

                证明1：

                        假设存在一个链A->N1->N2->...->Nn->B 

                                且这个链是A到B的最短路

                        则A->B的长度<A->N1的长度

                        即A->B不是A到B的最短路 

                        证得：命题1的逆否命题为真，故命题1为真 

                由命题1得：在初始情况下，必然能从与A直接相连的若干个点中找到一个

                               点，该点与A的直接距离就是其最短路径

        对后续情况，已知部分最短路径 

                设已经求出最短路的点集合为S{A,N1,N2,N3,...,Nn} 

                设A为初始点

                S外有一点B 

                命题2：

                        假设L3是A到B的最短路，Nan是路上一点，且Nan在S内 

                        假设L1是A到Nan的最短路

                        假设L2是Nan到B的最短路

                        则L1+L2=L3 

                证明2：

                        假设L4>L1，L4是A到Nan的另一条路 

                        假设L5>L2，L5是Nan到B的另一条路 

                则知：

                        L1+L2<L4+L5 

                        L1+L2<L1+L5

                        L1+L2<L4+L2

                由最短路定义得：

                        L3=L1+L2 

                命题2得证

                由命题2得：需要解决的问题从找最短路变成了找Nan

                核心优化（减治）： 

                        如果所有S内的点重合在一处，那么就不必找Nan了

                                此时L1=0，L2即是L3

                                而且A与Nan重合，故L2就是A到B的最短路

                                问题甚至转化成了初始情况：

                                        A与S外的点“直连”（即0+L2）

                                此时可以用初始情况的结论来解决下一个点 

操作总论：

        初始情况时，找到与A直连的最近的点B

        即求得B的最短路，并将之放入S中 

        为了保持所有S中的点与A重合在一处，

        需要将每次放入S的新点N做以下处理：

                1.设M与N直连，A到M的已知距离是L

                2.将L更新为min（L，A到N的最短路+M到N的距离） 

        这样处理之后，N点与A点可重合

                而A与S外点之间的距离又没有被这个操作影响