首页 > 代码库 > 《算法》C++代码 Dijkstra

《算法》C++代码 Dijkstra

       单源最短路,复杂度是O(N²),堆优化的是O(NlogN)。基本思想是贪心,每次都加入一个当前最近的点,可以证明每次当时最近的点就是当前最短的路径。因此,所有点都加入之后,起点到所有点的最短路径就都求出来了。

       在实现中,需要注意的是,在堆中的某个点i,不只要存当前到i的最短路径长度d[i],还得记上这是i点的长度。换句话说,要随时能知道i点的对应值d[i]在堆中的位置,和堆中某点H[k]对应的点i。我采用的方法,是在堆中用两个数组去维护这个一一对应的关系。

       下面给出本题的伪代码:

 1 d ← ∞,堆H为空 2 d[S]=0 3 for(所有点i) H.in(i,d[i]); 4 while(堆非空) 5 { 6     u=H.out(); 7     for(所有边u->v) 8         if(d[v]>d[u]+(u,v)) 9         {10             d[v]=d[u]+(u,v);11             H.update(v,d[v]);12         }13 }

       最后说一句,Dijkstra算法中,不仅不可以出现让最短路消失的负权环,也不可出现负权边。因为它是贪心的,一旦出现负权边,那么可能会先走一个比较长的边,再通过负权边走回来,达到更短的路径,这样Dijkstra的贪心思路就失效了。

       堆优化就不写了,有时间再补充吧。

《算法》C++代码 Dijkstra