我正在寻找用常规堆实现的Dijkstra算法的一系列输入，其中Dijkstra的实际复杂度将是Θ（（e + v）logv）。
我知道如何实现Dijsktra及其工作方式，我也理解最耗时的操作是将一个顶点添加到堆中并改变顶点的距离。但是，我不确定如何找到Dijkstra最坏情况输入的图形（图形序列）。
此外，如果您有关于如何找到最坏情况复杂性的输入序列的任何一般提示，那将是有帮助的。
让顶点从1到n编号，你想找到从顶点1到顶点n的路径。让e[i][j]成为边缘的长度，连接i和j。最初e[1][2] = e[2][3] = ... = e[n - 1][n] = 1。现在我们遍历从n - 2到1的顶点。在i的每个j的[i + 2, n]-th顶点，我们制作e[i][j] = e[i][i + 1] + e[i + 1][j] + 1。
现在我们有完整的图表。在每次迭代中，dijkstra将更新O(n)顶点，因此它是在O(n ^ 2) = O(E)中运行的O(log n)动作。
所以最终的渐近线将是O(n log(n) + E log(n))