我一直在尝试使用 Fibonacci 最小堆优化我的 Dijkstra 算法,根据此 1 [文章] 应该采用复杂度 $O(M+Nlog(N))$ 其中:
- M是边数
- N是顶点数
我已经计算了总体复杂度,但我不确定它是否正确,我很想得到一些建议:
首先也是最重要的是,我们有“声明和赋值”,我会尽量避免,因为它们都是常量基本操作,需要 $O(1)$ 并且对我的复杂性没有贡献 n $\to$ $\infty$.
第一个复杂度为 $O(N)$ 的 for 循环。
采用 $O(log(N))$ 的 headpop 方法假设我们在二叉堆中查找具有最小权重的节点。
这是我不确定的地方。所以我们从源中取出权重较小的节点,然后更新邻居的标签,这意味着我们转到邻接列表(在本例中为字典)并检查集合 $\delta^+(v) 中所有可能的边$,即从 v 到包含已访问节点的集合 $\S$ 中的另一个顶点 u 的所有节点。因此,完整图的总体复杂度为 $O(n-1)$。
考虑到所有这些,我最终得到: $O(N\cdot(log(N) + M))$ $\equiv$ $O(N\cdot(log(N) + N - 1)) $ $\equiv$ $O(N\cdot log(N) + N^2)$ $\equiv$ $O(N^2)$ 对于较大的 N 值。
这不是我希望从我的解决方案中得到的预期输出,因此我很高兴听到您的建议。
def dijkstra2(successors, s):
S = []; S.append(s)
n = len(successors)
L = dict(); L[s] = 0
P = dict(); P[s] = '-'
# Iterate through the V/{s}-nodes and set L[j] to infinity and P[j] to s.
for o in range(0, n):
if o != s:
L[o] = numpy.inf
P[o] = s
# Visited vector.
visited = [False] * n;
# Heapq
queue = [(0, s)];
while queue:
par_len, v = heappop(queue);
# v is unvisited
if visited[v] is False:
visited[v] = True
for w, edge_len in successors[v].items():
# Check if the child is unvisited and compute the distance.
if visited[w] is False and edge_len + par_len < L[w] :
heappush(queue, (edge_len + par_len, w))
L[w] = edge_len + par_len
P[w] = v
return L, P
最佳答案
Dijkstra 算法是:
O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|)
斐波那契堆:
O(|E| + |V| log |V|)
二叉堆:
O((|E| + |V|) log |V|)
E 是:
|E| = O(|V|^2)
问是: 最小优先级队列根据自己的当前距离估计对顶点进行排序。
初始化堆:
from heapq import *
from random import randint
f = FibonacciHeap()
h = []
n = 100
for i in xrange(0, n):
r = randint(1, 1000)
f.insert(r)
heappush(h, r)
打印运行时间代码:
import time
# test fib heap running time
start_time = time.time()
while f.total_nodes > 0:
m = f.extract_min()
print "%s seconds run time for fib heap" % (time.time() - start_time)
# test heapq running time
start_time = time.time()
while h:
m = heappop(h)
print "%s seconds run time for heapq" % (time.time() - start_time)
关于python - 使用 Fibonacci 最小堆的 dijkstra 的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56137981/