在例6-3的Dijkstra算法实现中，构造初始优先队列的循环将会执行V次插入操作，将会花费O(V log V)的时间。在剩下的while循环中，每条边都会被访问一次，因此decrease Key操作执行不会超过E次，花费O(E log V)的时间。因此，总开销是O((V+E)log V)。
图6-15详解描述的是Dijkstra算法的一个版本，这个版本适用于稠密图，使用的是一个邻接矩阵。例6-4中的C++实现更加简单，因为它避免了使用二叉堆。这个版本的效率是由如何快速在V-S中得到最小的dist。whilte循环将会执行n次，因为S每次只会增加一个顶点。在V-S中得到最小的dist[u]将要探测n个顶点。注意在while循环的内循环中，每条边都要被检测一次。因此，总运行时间为O(V2+E)。
图 6-15 稠密图的Dijkstra算法详解例6-4：稠密图的Dijkstra算法实现
我们可以更深入地优化例6-4，删除所有的C++STL对象，如例6-5所示。通过减少使用类的开销，我们能够得到令人印象深刻的性能改进，就如在随后“比较”一节中讨论的那样。
例6-5：稠密图的Dijkstra优化算法