在一个问题中，我得到了一个图G，它只有正权重，其直径(即G中每对顶点之间最短路径的最大值)=D。该问题要求一个单源最短路径算法比Dijkstra更快，运行时间O(V+e+D)。
到目前为止我所考虑的：我曾考虑过添加虚拟节点的方法，以便将G转换为未加权图G'，然后运行BFS，但这将导致复杂性：O(V+WE)
(如G’，E’=O(WE)和V=O(WE+V))
在我看来，D并没有真正帮助降低问题的复杂性，因为权重的总和(即要添加的虚拟节点的总数)与D无关。
将Djikstra的算法与优先级队列的优化版本结合使用。假设该图具有节点0..V-1。
优先级队列将由节点的双链表的数组Arr[0..D](索引在0和D之间的数组，包括0和3)、指示数组中所有节点的优先级与起始节点相距至少i的索引i以及数组location[0..V - 1]组成，其中location[node]的值是包含node的Arr中的双链表节点，或者如果不存在这样的节点则为CCD_ 10。当我们找到从起始节点到所讨论节点的长度为i的路径时，我们将节点存储在列表Arr[i]中。
将一个尚未存在的节点添加到优先级队列中是O(1)——如果我们有一个暂定距离s，那么我们将该节点添加到链表Arr[s]中，并相应地更新location[node]。请注意，如果优先级为>D，我们实际上应该避免将节点完全添加到优先级队列中，并确信稍后会将其添加到具有优先级<= D的队列中。
从优先级队列中删除给定节点也是O(1)——我们可以使用location[node]在O(1)中找到其双链表节点，从双链表中删除该节点，并将location[node]设置为null。当我们更改节点的优先级时，我们将需要此操作。
查找和删除最小节点不那么简单。我们不断地增加i，直到我们找到一些i，使得Arr[i]不为空。然后，我们从优先级队列中删除Arr[i]中的一个节点(也不要忘记更新location[node])。整个程序中完成的增量总数为D，因为我们将把i从0更改为D，每次增量一次。忽略增量，在这个过程中完成的其他工作是O(1)。
请注意，这是有效的，因为我们可以保证，一旦我们删除了优先级为i的节点，我们就永远不会将另一个优先级为<i的节点添加到优先级队列中。它之所以有效，是因为我们知道，我们永远无法实际删除添加到优先级为> D的优先级队列中的任何内容，因为只有当优先级队列的最终正确路径长度为<= D时，我们才能从优先级队列中删除某些内容-因此，没有必要向优先级为> D的优先级队列添加任何内容。这源于当图具有正边权重时Dijkstra算法的一般性质，以及图的直径为D的事实。
因此，根据需要，算法将为O(V + E + D)。