Dijkstra 算法 - 复杂度
Dijkstra's Algorithm - complexity
我在理解 Djisktra 算法的复杂性时遇到了一定的问题，希望有人能指正我。
对于我的例子，我取了一个有 n 个顶点的完整图。
您选择一个起始顶点，假设为 a1，标记它，然后计算边上的所有 n-1 个权重。 O(n)
你选最小的那个。假设顶点 a2 并标记它。 O(n)
之后，您计算边上的 n-2 个新权重，并寻找下一个尚未标记的顶点以添加您的标记顶点集。
等等...
算法运行直到您可以标记所有顶点。复杂度：n-1 + n-2 + ... + n - (n - 1) = Binom(n,2) 这是 O(n^2)，而不是 O(n*ln(n)) 我想。
我读到过很多次人们使用堆进行优化，但我仍然不知道如何避免 Binom(n,2) 计算。
我一定是在某些地方错了，但看不出哪里错了。
如果你有一个完整的图，那么你当然不能比 O(n^2) 做得更好——因为，那是你输入的大小。
如果您没有完整的图，并且将边存储在邻接表中，那么您可以做得更好。您仍然需要查看所有边，但是使用优先级队列可以管理 O(e + n log n)，其中 e 是邻接列表中的边数。
我在理解 Djisktra 算法的复杂性时遇到了一定的问题，希望有人能指正我。
对于我的例子，我取了一个有 n 个顶点的完整图。
您选择一个起始顶点，假设为 a1，标记它，然后计算边上的所有 n-1 个权重。 O(n)
你选最小的那个。假设顶点 a2 并标记它。 O(n)
之后，您计算边上的 n-2 个新权重，并寻找下一个尚未标记的顶点以添加您的标记顶点集。
等等...
算法运行直到您可以标记所有顶点。复杂度：n-1 + n-2 + ... + n - (n - 1) = Binom(n,2) 这是 O(n^2)，而不是 O(n*ln(n)) 我想。
我读到过很多次人们使用堆进行优化，但我仍然不知道如何避免 Binom(n,2) 计算。
我一定是在某些地方错了，但看不出哪里错了。
如果你有一个完整的图，那么你当然不能比 O(n^2) 做得更好——因为，那是你输入的大小。
如果您没有完整的图，并且将边存储在邻接表中，那么您可以做得更好。您仍然需要查看所有边，但是使用优先级队列可以管理 O(e + n log n)，其中 e 是邻接列表中的边数。