如何证明dijkstra 算法是全局最优算法

2025-02-11 17:57:30

推荐回答（2个）

回答1：

证明：
（I）首先考虑最简单的情况，找找思路。
由于现在只知道S到S的最短距离，也就是0，所以第一步只能考虑从S出发直接到达各点的距离(显然在这个时候考虑路径存在中间顶点没有意义，因为你不能确定S到这个中间顶点的最短路径)。得到S直达各点的w(S,V_i)，i=1,2,...,n-1，与w[0,i]比较，w[1,i]保存小值。
这个时候，Dijkstra的做法是选出所有d[0,i]，i=0...n-1，为false的对应的w[1,i]，i=0...n-1，中的最小值w[1,k]并认为这就是源点S到目标顶点V_k的最短距离。这很好理解，因为假设S到V_k的最短距离是另外一条路径，则必然存在一个中间顶点，不妨设为V_u，u=0...n-1，则有w(S,V_u) + w(V_u, V_k) < w(S,V_k)，那么必有w(S,V_u) < w(S,V_k)，显然，这与w[1,k]是最小值矛盾，所以w[1,k]就是S到V_k的最短距离，此时把d[1,k]标记为true。
算法的中间值如何得出：
其实以上的叙述已经说明了中间值是如何得到的。设w[x,y]是当前刚确定的源点S到目标定点V_y的最短距离，其中x=0...n-1，y=0...n-1，对所有d[x,i]，i=0...n-1，为false的点，更新w[x+1,i]为w[x,i]与(w[x,y]+w(V_y,V_i))的较小值。（I）里的w[x,y]就是w[0,0]。
（II）现在考虑一般情况
设已求得一个集合A，|A|=k，现在求S到第(k+1)个点(注意不一定是V_(k+1)，这里的k只是A的基数而已)。
设w[k-1,u]，u=0...n-1，是在集合A的基数为k时，所有未访问的w[k-1,i]，i=0...n-1，保存的中间值中的最小值(也就是最后一个纳入集合A的顶点，k-1-0+1=k)。标记d[k-1,u]为true，对所有w[k,i]，更新d[k-1,i]为false的w[k,i]的值，使其为w[k-1,i]与w[k-1,u]+w(V_u, V_i)的较小值，然后选出d[k,i]为false的所有w[k,i]的最小值w[k,p]，p=0...n-1，即源点S到目标顶点p的最短距离，标记d[k,p]为true，继续这一过程，直到某一次求出的最小值为int.MaxValue(表示之后的点都不能到达)。
道理仍然是一样的，如果这个最小值w[k,p]不是源点S到顶点V_p的最短距离，那么设S经过顶点V_t然后到达V_p(V_t是这条路径的倒数第二个顶点)。V_t存在两种可能，要么属于集合A但不是顶点V_u，要么属于集合B。
（i）如果V_t属于A但不是顶点V_u，由于每一个中间值在每求出一个最短距离时都是比较过的，也就是说，在求出S到V_t的最短距离时，S->V_t->V_p的长度必然是和原来的S->V_p的路径长度比较过的，一定会保存下来，则不可能得到当前这个w[k,p]，w[k,p]里保存的应该是S经过V_t到V_p的长度而不是S经过V_u到V_p的长度。
（ii）如果V_t属于B，不妨设这条路径为S->V_r->V_o->V_t->V_p，其中V_r属于A，V_o，V_t可以是同一点，也可以是不同点，但是他们都不属于A而是属于B，那么显然有S->V_r->V_o的长度小于S->V_r->V_o->V_t->V_p的长度小于w[k,p]，即w[k,o] < w[k,p]，与w[k,p]是最小值矛盾。
(iii) 如果路径为S->V_t->V_p且V_t属于B，那么显然S->V_t比S->V_p要近，也就是说，在选择下一个最小值的时候，应该选择w[s,t]而非w[s,p]。
所以，这样一个顶点V_t不存在，一般情况得证。
证毕。

回答2：

题主去看算法导论单源最短路径那章有详细的证明过程

最新问答

在国外考雅思和国内有什么异同？

大一统计学，圈起来的题目，求解

梦见别人家白事变红事

我是开油坊的，如果用离心机过滤的油沉淀6天了，油清就是有白色漂浮物不沉淀怎么回事？

玻璃注射器不带针头能带上飞机不

手工羊绒衫怎么织，从下往上织的，袖口怎么留

新疆和合珠宝玉器股份有限公司北京海淀分公司怎么样？

用焗油染回黑色，但现在头发一直在褪色，怎么办，要到什么时候才好啊

求解此配置能不能运行剑网3安史之乱？

美菱冰箱BCD-352WPBH，我已经付钱买了这款冰箱，可是怎么也查不到这款型