August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
图算法
｜
151
图算法
表
6
-
2
：在稠密图上计算单源顶点最短路径的时间
V
/ 个
E
/ 条 使用优先队列的 针对稠密图优化的 Bellman-Ford 算法
Dijkstra 算法 Dijkstra 算法
980 479,710 0.0681 0.0050 0.1730
1,621 1,313,010 0.2087 0.0146 0.5090
6,117 18,705,786 3.9399 0.2056 39.6780
7,663 29,356,953 7.6723 0.3295 40.5585
9,847 48,476,781 13.1831 0.5381 78.4154
9,882 48,822,021 13.3724 0.5413 42.1146
6.6.3 稀疏图
大型图通常是稀疏的，图
6-3
的结果确认了使用优先队列的
Dijkstra
算法
更加适合于稀
疏图。注意，针对稠密图的实现明显慢很多。表格中的行按照稀疏图中的边数排序，因
为这样可以明显地看出结果中的费用因子。
表
6
-
3
：在大型稀疏图上计算单源顶点最短路径的时间
V
/ 个
E
/ 条 稠密度 使用优先队列的 针对稠密图的优化后的
Dijkstra 算法 /s Dijkstra 算法 /s
3,403 137,845 2.4% 0.0102 0.0333
3,243 294,276 5.6% 0.0226 0.0305
19,780 674,195 0.34% 0.0515 1.1329 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.