4005-741-01 Advanced Computer Networks
Module 1A. Theory -- Data Structures and Algorithms
Lecture Notes

Data Structures: Heaps and Priority Queues

• Jon Bentley. Programming Pearls: Thanks, Heaps. Communications of the ACM, 28(3):245−250, March 1985.
  [PDF]

• Array representation and invariants

• Basic operations: sift-up, sift-down

• Priority queue operations: insert, extract-min, decrease-key

• Asymptotic running times

• Applications: shortest path algorithm, discrete event simulation

Data Structures: Graphs

• Terminology: Vertices, edges, adjacency, weights, undirected, directed, connected components

• Adjacency list representation; pros and cons

• Adjacency matrix representation; pros and cons

Graph Algorithms: Depth First Search

• Algorithm for an undirected graph consisting of one connected component

  For all vertices V:
      visited[V] = false
  DepthFirstSearch (starting vertex)
  
  DepthFirstSearch (Vertex V)
      If not visited[V]:
          Application specific processing for V goes here
          visited[V] = true
          For each vertex W adjacent to V:
              DepthFirstSearch (W)
  

Graph Algorithms: Shortest Paths

• Given a weighted graph, where the edge weights represent distances

• Find the length (total distance) of the shortest path from a given starting vertex to every other vertex

• Find the predecessor of each vertex along the shortest path from a given starting vertex

• Dijkstra's Algorithm

  For all vertices V:
      distance[V] = infinity
  distance[starting vertex] = 0
  Put all vertices into a minimum priority queue by distance
  While queue is not empty:
      V = Extract minimum vertex from queue
      For each vertex W adjacent to V:
          If distance[W] > distance[V] + weight[V,W]:
              predecessor[W] = V
              distance[W] = distance[V] + weight[V,W]
              Decrease key of W in queue
  

• Applications: unicast routing

Graph Algorithms: All-Pairs Shortest Paths

• Given a weighted graph, where the edge weights represent distances

• Find the length (total distance) of the shortest path from every starting vertex to every other ending vertex

• Assumes the edge weights are stored in an NxN adjacency matrix
  • N = number of vertices
  • D[i,j] = weight of edge between vertices i and j

• Floyd's Algorithm

  For i = 1 to N:
      For r = 1 to N:
          For c = 1 to N:
              D[r,c] = min (D[r,c], D[r,i] + D[i,c])
  

Graph Algorithms: Minimum Spanning Tree

• Given a weighted graph, where the edge weights represent distances

• Spanning tree = Subgraph such that:
  • All vertices included
  • Some or all edges included
  • There is exactly one path between any two edges (subgraph is a tree)

• Minimum spanning tree = Spanning tree such that:
  • Sum of edge weights is as small as possible

• Find the predecessor of each vertex along the minimum spanning tree from a given starting vertex

• Prim's Algorithm

  For all vertices V:
      minweight[V] = infinity
  minweight[starting vertex] = 0
  Put all vertices into a minimum priority queue by minweight
  While queue is not empty:
      V = Extract minimum vertex from queue
      For each vertex W adjacent to V:
          If W is still in the queue and weight[V,W] < minweight[W]:
              predecessor[W] = V
              minweight[W] = weight[V,W]
              Decrease key of W in queue
  

  (minweight[V] is the smallest weight between vertex V and any vertex in the minimum spanning tree)

• Note the similarity to Dijkstra's Algorithm

• Applications: multicast routing

Graph Algorithms: Maximum Flow

• Given:
  • A directed graph
  • Each edge labeled with a capacity
  • A source vertex
  • A sink vertex

• Find:
  • A pattern of flow from source to sink, such that
  • Each edge's flow is less than or equal to the edge's capacity, and
  • The total flow is as large as possible -- Maximum Flow

• (For an undirected graph, replace each undirected edge with two directed edges in opposite directions)

• Ford-Fulkerson Algorithm
  1. Start with each edge's flow = 0 and each edge's capacity as given.
  2. Find a path P from source to sink such that:
     1. There are no cycles in P, and
     2. There is unused capacity (flow < capacity) along each edge in P.
  3. Let F be the smallest unused capacity among all the edges in P.
  4. For each edge in P, add F to the edge's flow.
  5. Repeat Steps 2-4 until there are no more possible paths.
  6. For each pair of mutually adjacent vertices (X, Y), compute the net flow between X and Y = (flow from X to Y) - (flow from Y to X).

• Sum of flows coming out of source
  = Sum of flows going into sink
  = Maximum flow from source to sink

• Example

  Graph:		Maximum flow from A to F = 12:

• Example

  Graph:		Maximum flow from D to F = 8:

  (In this example there are other flow patterns that yield the same maximum flow)

• Applications: alternative routing methods; network connectivity analysis

Advanced Computer Networks • 4005-741-01 • Fall Quarter 2009

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2009 Alan Kaminsky. All rights reserved. Last updated 08-Sep-2009. Please send comments to ark­@­cs.rit.edu.