首页 > 代码库 > 《算法》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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。