把之前不求甚解的地方补上，顺带一提，最小生成树的prim算法和狄杰斯特拉基本一模一样
狄杰斯特拉算法其实和红黑树有点像，两者都是先弄出一个具有某种性质的集合，接着不断向这个集合中插入元素并进行维护，以确保这个集合一直满足某种性质，直到所有需要处理的元素都在这个集合中，自然也就完成了算法的目的，这种思路很有学习的价值
狄杰斯特拉中具有某种性质的集合是d【】数组，用于记录“以某个点作为起点，到当前节点的最短路径”，现在我们已经得到了集合，下一步就是要向集合中不断插入元素，并找到某种维护方式，使d【】数组一直保持这个性质，如何维护狄杰斯特拉就不多赘述，重点讲讲为什么这么维护是正确的
1.为什么每次要选择当前d【】最小的元素作为更新的起点？
贪心
以红黑树的插入为例，红黑树中插入的节点一定是红色而不是黑色，这是因为如果插入红色节点，只是有可能破坏红黑树的性质从而导致要进行维护，而如果插入黑色节点，则一定会破坏红黑树的性质从而必须进行维护，同样的道理，所有d【】对应的节点中，当前已知的，d【】最小的元素显然是最有可能在最短路中的，再换个角度，d【】最小的元素，离起点最近（也就是到起点的距离最小），所以每次更新，都相当于是在目前已知的，最短路的结尾进行下一步的更新
2.如何保证每次松弛操作完，不会破坏d【】中的性质？
假设此时正在更新第x个元素，那么对于前x-1个元素中的任意一个元素y来说，只有两种情况，第一种，松弛操作的时候松弛到y了，这种情况下只需要比较原本的d【】和从当前这条路过来的距离谁更短，让短的那个成为新的d【】，这样就没有破坏d【】的性质，其中保存的依旧是最短路的长度，第二种，这次松弛与y无关，那么这次操作自然就不会改变与y有关的d【】，当前的d【】依旧保持性质
有问题欢迎指出
标签：特拉,正确性,元素,集合,狄杰斯,插入,性质 From： https://www.cnblogs.com/pcpcppc/p/17785629.html