- Forward


Data Structures for Routing
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review
Back Forward
  • 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
Back Forward
  • 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
Back Forward
  • 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
Back Forward
  • 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.)
Back Forward
  • 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.)
Back Forward
  • 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
Back -