先回顾下上节课的内容:
下面来看一个定理:对于所有的点来说,放松操作总是满足 d[v] ≥ δ(s, v)。即点s到点v的最短路径总是小于或等于当前点d的路径权重。证明如下:
在正是进入复杂的图前,先看个简单的有向非循环图DAG(Directed Acyclic Graphs),内无负循环。下图是讲DAG如何找最短路径:
如果有循环且无负权重边呢?可以使用Dijkstra算法,具体如下:
由于Dijkstra算法有三个主要操作:插入点的优先队列,抽取最小优先值,减键操作。所有最后Dijkstra的时间复杂度可约为θ(v2)。如果用BInary min-heap,extract-min是θ(lgv),decrease-key是θ(lgv),最后为θ(lgv+Elgv)。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章