[MIT6.006] 16. Dijkstra
阅读原文时间:2023年07月11日阅读:1

先回顾下上节课的内容:

下面来看一个定理:对于所有的点来说,放松操作总是满足 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)。

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章