Dijstra proof
看到09CS 考研DS第一道大题，是对Dijstra的变形，问是否正确，于是回顾这一经典的greedy算法。
算法思想和代码之前已经联系过了，但是这道题目涉及到了正确性证明，如果变形了是否保证正确性，尽管答案只是举了一个反例来说明，但是我还是打算回顾下
当时的proof。其实一直都不算真正意义的理解了。
利用数学归纳的思想：
集合分为close-set表示，已经算出最短路径的点击，open-set为剩余的点击。
1(初始条件). 一开始肯定是source点u了，因为dist为0，不可能有比他更短的了。假设第二个点p，现在证明p一定是u->p为p的最短路径。
假设不是，假设存在open-set点x，使得u->x x->p为最短路径，那么u->x一定比u->p短(边>0的性质)，x应该比p先加入close-set，与一直矛盾
2(递推证明).加入当前close-set有些点，那么现在加入p，那么u->p的最短路径的点一定都在close-set里。
假设不是，假设路径出现了一个点x在opens-set(假设只是路径最后一个点在open-set,其他情况是转化为这个的吧),那么u->x x->p比u->p(中间全是close-set中点)要短，那么u->x比u->p短，x应该比p先加入close-set，
产生矛盾。
思路来源这里
http://blog.csdn.net/dog250/article/details/5303310
另外还附上一个童鞋另一种思维方式的理解正确性 http://my.oschina.net/mustang/blog/56216
当年算法书的证明感觉不make sense，所以弃掉了。
另外今天看到了一个priority_queue 也是在
STL与堆相关的主要是 make_heap push_heap, pop_heap 这样一些algorithm里的函数，用vector容器来装，可以实现heap