《算法技术手册》比较

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

·Bellman-Ford：O(V*E)

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

·使用优先队列的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倍左右。表格中的行依稀疏图中的边数排序，因为这样可以明显地看出结果中的开销因子。