Loading Web-Font TeX/Math/Italic
Data Structures for Routing
An Introduction
|
Prof. David Bernstein
James Madison University
|
|
Computer Science Department
|
bernstdh@jmu.edu
|
Review
Worst Case Time for Dijkstra's Algorithm
- Size of the Problem:
-
m vertices/nodes
-
n edges/arcs/links
- The "Outer Loop":
- Start at the origin
- Move to the next permanent node [O(m)]
- The "Inner Loop":
- Update each node's label [O(m)]
- Search the nodes to find the smallest temporary
label [O(m)]
-
Overall:
- 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)]
- So, the complete algorithm is O(m \log m + n)
There's Always More to Learn
MathJax Math Υ