If \(T_{1}= O[f_{1}(m)]\)
and \(T_{2}= O[f_{2}(m)]\)
then \(T_{1}T_{2}=O[f_{1}(m)]O[f_{2}(m)]\)
So, this algorithm is \(O(m^{2})\)
Updating Labels
One Observation:
The only labels that can change are those that
are associated with nodes that can be reached from the
working node
So, each node should have a collection of reachable nodes
unless the graph is complete
Another Observation:
Each node can only be updated
as many times as there are inbound arcs
In the worst case this is \(O(n)\)
Finding the Smallest Temporary Label
One Observation:
A relatively small number of nodes will have a finite label
(especially in early iterations)
Hence keeping a collection of nodes with
temporary finite labels will improve running time
in practice
Another Observation:
It is not efficient to completely sort the collection of
candidates each iteration (Why not?)
It would be nice if we could keep the collection
"partially sorted"
Finding the Smallest Temporary Label (cont.)
Using "Buckets":
Have more than one collection for temporarily labeld
nodes
Each "bucket" contains a specific range of labels (e.g.,
0-100, 101-200, ...)
Note: The buckets can be kept in a circular structure
Buckets with Integer Labels:
Have one bucket for each possible label value
Keep track of the smallest bucket that currently has
any elements
Finding the Smallest Temporary Label (cont.)
Using a d-Heap:
A d-heap
is a tree with
the property that
a parent's "value" is not smaller than the "value"
of any of its d children
Removing the smallest element is \(O(\log m)\)
(as is adding an element)
Efficiency Bounds Revisited:
Each node can only be updated as many times as there
are incoming arcs, hence all of the nodes in total can
only be updated as many times as there are arcs, hence
the total running time for updating labels is
\(O(n)\)
For each of the possible \(m\) iterations
of the outer loop we must adjust the heap
[\(O(\log m)\)], find the best candidate
[\(O(1)\)], and remove the best candidate from the
heap [\(O(\log m)\)]