Dijkstra算法执行时，dist[v]表示的是根据S集中的顶点组成的子图，我们能够找到的从源点s到v的最短路径的最大长度。并且，对于每一个顶点v∈S，dist[v]为整数。幸运的是，Dijkstra算法不需要真正地计算和存储集合S。它只初始创建一个包含所有V中的顶点的集合，然后每次从集合中拿出一个顶点，计算出正确的dist[v]值；为了方便起见，我们使用V-S来记录这个集合。当所有的顶点都被访问或者为被访问的顶点都是源点不可达时，Dijkstra算法结束。
图 6-14 Dijkstra算法扩展S集在例6-3的C++实现中，我们使用了优先队列来存储V-S中的顶点。在这里优先队列是二叉堆，因为我们可以在常数时间寻找到优先级最小的顶点（优先级是顶点到s的距离）。此外，当s到v的最短路径找到之后，dist[v]的值减少，那么堆也必须修改。幸运的是，二叉堆形式的优先队列decreaseKey操作在平均情况下花费时间为O(log q)，q是二叉堆中顶点的数目，q永远小于或者等于顶点的总数n。
例6-3：使用优先队列的Dijkstra算法实现