Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• The Shortest-Path Problem.
• Dijkstra's Shortest-Path Algorithm.
• Analyzing Dijkstra's Shortest Path Algorithm.
• All Pairs Shortest Path Algorithms.
• The Floyd-Warshall Algorithm.

Preliminaries

Admin

• I apologize for the delay in getting exams back to you. It's near the top of my list, but keeps getting bumped down by other things.
• Homework due Wednesday.
  • Implement the naive version of the algorithm described in Section 6-2 and determine the average distance the arm travels on sets of 10, 20, and 40 random inputs in where each coordinate is between 0 and 99.
  • Implement the clever version of the algorithm described in Section 6-2.
  • Do problems 6-1a (just left graph; ec for right graph), 6-5, 6-6, 6-12.
• https://en.wikipedia.org/wiki/David_Phillips_%28entrepreneur%29

Extra Credit

Academic

• Cool Physics talk on Tuesday.
• CS Table Tuesday: Cryptographic Back Doors.
• Innovation Talk Wednesday.
• CS Extras Thursday: Mobile Sensing (UIowa).

Peer

• Sound art performance tonight in Quad at 8pm.
• Seth and company at Gardner Thursday 8:30.
• Orchestra Saturday at 7:30 p.m. in SL.

Questions

Problem 6-1 is too much work. Fixed.

How do you do max-flow? Look it up in the book.

What is a data structure? An arrangement of memory.

The Shortest-Path Problem

Given a weighted graph and two designated vertices (start and finish; source and sink), find the shortest path from one vertex to the other.

Dijkstra's Shortest-Path Algorithm

Find the shortest distance from A to every other node!

Node predecessor[n] // Predecessor on shortest path
int distance[n]     // Distance to node; initialize to infinite
boolean processed[n]// Have we processed node n.

distance[source] = 0
while there are unprocessed nodes
  find u, the unprocessed node with the shortest distance
  mark u as processed
  for each edge (u,v)
    if (distance[u] + weight[u,v] < distance[v])
      predecessor[v] = u
      distance[v] = distance[u] + weight[u,v]

An Example

Analyzing Dijkstra's Shortest Path Algorithm

• How do we find the unprocessed node with the shortest distance?
  • Iterate through the distance array. O(n)
  • Some kind of heap. O(logn)
• What's the running time of Dijkstra's algorithm?
  
  • O(n^2), if we use the naive version of shortest distance.
    • Why don't we write O(n^2 + m), since we have to pay attention to the edges, too? (See analysis below.) m is in O(n^2)
  • O(nlogn + m), if we use the heapy version of shortest distance
    • Analysis part 1: n repetitions of an O(logn) step
    • Analysis part 2: every edge is processed once at a cost of O(1), assuming we use adjacency lists.
• How does this differ from Prim's algorithm?
  • Prim's uses "distance from MST", Dijkstra's uses "distance from source"
  • Prim's is only for undirected graphs; Dijkstra's is for directed graphs.
• How do we know that it's correct?
  • Proof by contradiction?

All Pairs Shortest Path Algorithms

I want the cost of the shortest path from each node to every other node.

I could run Dijkstra's algorithm with every point as the starting point.

Running time: O(((n^2)*(logn)) + nm)

Floyd-Warshall

An O(n^3) algorithm that is generally much faster than "Run Dijkstra's n times".

We will number the nodes from 0 to n-1. Build the shortest path from each node to every other other node that only use nodes 0 .. k as intermediate nodes. Example and further discussion next time.