先回顾下上节课的内容：

下面来看一个定理：对于所有的点来说，放松操作总是满足 d[v] ≥ δ(s, v)。即点s到点v的最短路径总是小于或等于当前点d的路径权重。证明如下：

在正是进入复杂的图前，先看个简单的有向非循环图DAG（Directed Acyclic Graphs），内无负循环。下图是讲DAG如何找最短路径：

如果有循环且无负权重边呢？可以使用Dijkstra算法，具体如下：

由于Dijkstra算法有三个主要操作：插入点的优先队列，抽取最小优先值，减键操作。所有最后Dijkstra的时间复杂度可约为θ(v²)。如果用BInary min-heap，extract-min是θ(lgv)，decrease-key是θ(lgv)，最后为θ(lgv+Elgv)。

最新文章

1. onselectstart="return false"
2. Linux学习之五——压缩与备份
3. 在SourceInsight中用快捷键打开文件所在的目录
4. ZOJ 3367 Counterfeit Money（最大相同子矩阵）
5. vc6.0 通过ADO(udl)连接sql 2008
6. git add 命令详解
7. 【CSS】Intermediate2:Pseudo Classes
8. mysql的日志
9. C++之static_cast, dynamic_cast, const_cast
10. OSX下编译安装opencv3.1.0与opencv_contrib_master
11. 微信小程序wx.navigateTo层叠5次限制，特殊情况的建议
12. codeforces#766 D. Mahmoud and a Dictionary （并查集）
13. 转 .NET4.5之初识async与await
14. vue 去哪网项目 学习笔记(一)
15. mysql 问题：连不上
16. github咋用昂
17. Github笔记（1）
18. Ng第十三课：聚类(Clustering)
19. 2.2《想成为黑客，不知道这些命令行可不行》(Learn Enough Command Line to Be Dangerous)——列表
20. 360加固保的dex脱壳方法

热门文章

1. javascript 数据类型判断总结
2. .net 手动建DataTable 获取DataTable列名 修改DataTable 列的顺序
3. nginx优化:worker_processes/worker_connections/worker_rlimit_nofile
4. 分布式事务说的的2PC、3PC、TCC是啥
5. 报错 source-1.6 中不支持 diamond运算符
6. app反编译遇到360加固,傻瓜式脱壳
7. SpringBoot整合Apache-CXF实践
8. 使用Volley获取验证码
9. LruCache缓存bitmap(二)
10. Promise 配合 axios 使用