Theorem : The complexity of Algorithm 1 is O(|E|·lg(|V|))
Proof: Because each node must be enqueued into and extracted from the queue
exactly once, and each link can cause at most one decrease-key operation, the
total queue operation time in Algorithm 1 is at in O(N·enQ + N·exQ + M·dkQ).
Beside queue operations, some manipulations are called at most twice for each
of the M links, i.e., changing their next-hop sets, while other operations are
called once for each of the N nodes to set their attributes. Each of them can be
implemented in constant time, and they cost O(N + M) in total. So the time
complexity of Algorithm 1 is still in O(N·enQ + N·exQ + M·dkQ). Since there
are at most S nodes in the queue, enQ = O(1), exQ = lg(N) and dkQ = O(1)
when the queue is implemented as a heap, and the total time complexity is in
O(|M|lg|N|). By substituting N by |V | and M by |E|, the complexity of
Algorithm 1 is now O(|E| · lg(|V |)).
Dostları ilə paylaş: 
