比较

下面的列表比较了三个算法的期望性能:

·Bellman-Ford:O(V*E)

·在稠密图上的Dijkstra算法:O(V2+E)

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

·使用优先队列的Dijkstra算法:O((V+E)*log V)

我们在不同的情况下比较这些算法。当然,为了选择最适合你手上数据的算法,你也可以像我们这样进行基准评测。我们将会执行算法10次,然后抛弃最好和最坏的结果,表格中的结果是剩余8次的平均值。

基准测试数据

产生一个“随机图”是非常困难的。在表6-2中,我们使用的是有V=k2+2个顶点,以及E=k3-k2+2k条边的图(图的构造细节参见代码库中的实现)。注意边的数目大概是n1.5,n是顶点的数目。使用了优先队列的Dijkstra算法的性能最好,Bellman-Ford的性能紧随其后。我们可以看到变种在稠密图上并没有多大性能改进。

阅读 ‧ 电子书库

稠密图

在稠密图中,E大约是O(V2);例如,在一个有着n个顶点的完全图中,存在n(n-1)/2条边。我们不推荐在这样的稠密图上使用Bellman-Ford,因为这样的性能将会退化至O(V3)。表6-3的稠密图是来自于研究人员研究旅行商问题(TSP)[1]时使用的数据。我们进行了100次实验,抛弃最好和最坏的结果,表中的结果是剩余98次的平均值。虽然在优先队列和稠密图版本的Dijkstra算法之间存在一点点差异,但是优化过后的Dijkstra算法的性能得到了非常大的改进,如表中的第5列所示。在最后一列中,我们给出了在同样的问题上,Bellman-Ford算法的性能,但是结果只是五次执行结果的平均值,因为性能退化得太厉害了。从最后一列我们知道,Bellman-Ford算法在小图上的绝对性能看起来还是合理的,但是相比其他算法,在稠密图上使用这个算法就是一个错误。

阅读 ‧ 电子书库

稀疏图

大图通常是稀疏的,图6-4的结果确认了,使用优先队列的Dijkstra算法更加适合稀疏图,为稠密图设计的实现慢10倍左右。表格中的行依稀疏图中的边数排序,因为这样可以明显地看出结果中的开销因子。

阅读 ‧ 电子书库
[1]http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/。