迪杰斯特拉算法的证明
求V0到V8的最短距离：
迪杰斯特拉算法的思想是依次求出距离V0第1近，第2近…….一直到第8近，也就是从距离V0最近到最远的点。而每求一个最近距离就修正V0到剩下点的最短距离。
设A为包含V0和已经求得最短距离的点，B为A的补集。现在需要证明的是：
从上一次求得的V0到剩下各点的距离中选出最短的设为Vn，该距离（即V0Vn）即为所有路径中V0到Vn的最短路径。其实也是下一个（即除A中点之外）最短距离
证明：只需要证明V0到Vn的上一个中转站一定带A中。
反证法：假设此点在B中，设为Vn-1，则意思就是V0Vn-1+Vn-1Vn<此时的V0Vn,既然如此，那意味着V0Vn-1
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！