Dijkstra

朴素版Dijkstra

时间复杂度O(n^2)

1. 初始化距离 dist[1]=0;其他所有的点 dist[i] = ∞
2. for( 每一个点 ){
       t < -- 不在S中的距离最近的点
       S < -- t
       用t去更新其他点的距离 如果dist[t] + w < dist[x] 就更新
       这样更新了每一个点 最后都是到1号点的最短距离
   }

堆优化的Dijkstra

时间复杂度O(mlogn)

1. 初始化距离 dist[1] = 0(1号点距离1号点的距离为0),其他点 dist[i] = ∞ S : 当前已经确定最短路的点
2. 2.for( 每一个点 ){
       t < -- 不在S中的距离最近的点
       S < -- t
       用t去更新其他点的距离 如果dist[t] + w < dist[x] 就更新
       这样更新了每一个点 最后都是到1号点的最短距离
   }
   ” t < -- 不在S中的距离最近的点” 把这一步用最小堆优化一下，因为每次都是找最小的点
   选择使用哪种堆 如果是手写堆 需要down 和 up两个操作比较麻烦 mlogn
   如果是priority_queue 是mlogm 但是 m≈n^2 所以2mlogn 是一样的

算法流程：

1. 首先初始化所有的边为 正无穷
   更新1号节点的距离 0
2. 把1号节点加入到堆中 heap.push({0,1})
   while( 堆不空 ){
       取出堆的头
       pop();
       加入到集合中 st[t] = true;
       for(当前最小距离的点的next节点){
           if( 满足距离条件 ){
               更新距离
               把当前点加入到堆中
           }
       }
   }