具有正权值和直径D的图的单源最短路径

Question

在一个问题中，给出了一个只有正权值及其直径(即G中每对顶点中最大最短路径)= D的图G。该问题要求一个单源最短路径算法，该算法比Dijkstra快，在O(V+E+D)时间内运行。

到目前为止，我考虑的是:我考虑了添加虚拟节点的方法，以便将G转换为一个无权图G‘，然后运行BFS，但这将导致复杂性为: O(V+WE)。

(如G'，E‘= O(WE)和V= O(WE+V))

在我看来，D实际上并不能降低问题的复杂性，因为权重之和(即要添加的虚拟节点总数)与D无关。

Answer 1

在优先级队列的优化版本中使用algorithm的算法。假设图有节点0..V-1。

优先级队列将包括双链接节点列表的数组Arr[0..D] (索引介于0和D之间的数组)，以及表示数组中所有节点的优先级与起始节点至少距离i的索引i，以及数组location[0..V - 1]，其中location[node]的值是包含node的Arr中的双链接列表节点，如果没有这样的节点，则为null。当我们找到从开始节点到相关节点的长度为i的路径时，我们会在列表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)。