Data Structures for Routing

Data Structures for Routing
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Review

Routing Algorithms:
- Label setting methods
- Label corecting methods
Data Structures for Graphs/Networks:
- Contiguous
- Linked
We Have Not Considered:
- Do the data structures have an impact on the performance of the algorithms?

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)\)