1Graph Algorithms: Shortest PathsCS211Fall 20002Sorting in Linear TimeThere are several sorting methods that take linear time■ Counting Sort● sorts integers from a small range: [0..k] where k = O(n)■ Radix Sort● the method used by the old card-sorters● sorting time O(dn) where d is the number of “digits”■ How do these methods get around the Ω(n log n) lower bound?● They don’t use comparisons■ What sorting method works best?● QuickSort is best general-purpose sort● Counting Sort or Radix Sort can be best for some kinds of data3Aside: An Open Question on Sorting How long does it take to a sort an n-by-n table of numbers?■ O(n2log n) because there are n2numbers in the tableWhat if it’s an addition table?■ Shouldn’t it be easier to sort than an arbitrary set of n2numbers?n-by-n+135823571010 11 13 15 1812 13 15 18 2014 15 17 19 224Recall Digraphs■ Adjacency Matrix● Space O(v2)g[u][v] is true iff there is an edge from u to v■ Adjacency List● Space O(e+v)The list for u contains v iff there is an edge from u to v032 13T2T1TT0321032101 3205Recall Weighted Digraphs■ Adjacency Matrixg[u][v] is c iff there is an edge of cost c from u to v■ Adjacency ListThe list for u contains v,c iff there is an edge from u to v that has cost c032 1382201111503210321015811201 150 82 203 116Goal: Find Shortest Path in a Graph■ Finding the shortest (min-cost) path in a graph is a problem that occurs often● Find the least-cost route between Ithaca and Detroit● Result depend on our notion of cost▲ least mileage▲ least time▲ cheapest▲ least boring● All of these “costs” can be represented as edge costs on a graph■ How do we find a shortest path?27Shortest Paths for Unweighted GraphsbfsDistance(s):// s is the start vertex// dist[v] is length of s-to-v path// Initially dist[v] = ∞ for all vdist[s] = 0;Q.insert(s);while (Q nonempty) {v = Q.get();for (each w adjacent to v) {if (dist[w] == ∞) {dist[w] = dist[v]+1;Q.insert(w);}}}S BAC D EF8Analysis for bfsDistance■ How many times can a vertex be placed in the queue?■ How much time for the for-loop?● Depends on representation▲ Adjacency Matrix: O(v)▲ Adjacency List: O(ev)■ Time:● O(v2) for adj matrix● O(e+v) for adj listbfsDistance(s):// s is the start vertex// dist[v] is length of s-to-v path// Initially dist[v] = ∞ for all vdist[s] = 0;Q.insert(s);while (Q nonempty) {v = Q.get();for (each w adjacent to v) {if (dist[w] == ∞) {dist[w] = dist[v]+1;Q.insert(w);}}}9If There are Edge Costs?■ Idea #1● Add false nodes so that all edge costs are 1● But what if edge costs are large?● What if the costs aren’t integers?■ Idea #2● Nothing “interesting” happens at the false nodes● Can’t we just jump ahead to the next “real” node● Rule: always do the closest (real) node first● Use the array dist[ ] to ▲ Report answers▲ Keep track of what to do next10Dijkstra’s Algorithm■ Intuition● Edges are threads; vertices are beads● Pick up at s; mark each node as it leave the table■ Note: Negative edge-costs are not allowed● s is the start vertex● c(i,j) is the cost from i to j● Initially, vertices are unmarked● dist[v] is length of s-to-v path● Initially, dist[v] = ∞, for all vdijsktra(s):dist[s] = 0;while (some vertices are unmarked) {v = unmarked vertex with smallest dist;Mark v;for (each w adj to v) {dist[w] = min[ dist[w], dist[v] + c(v,w) ];}}S BAC D EF549211219211Dijkstra’s Algorithm using Adj Matrix■ While-loop is done v times■ Within the loop● Choosing v takes O(v) time● For-loop takes O(v) time■ Total time = O(v2)● s is the start vertex● c(i,j) is the cost from i to j● Initially, vertices are unmarked● dist[v] is length of s-to-v path● Initially, dist[v] = ∞, for all vdijsktra(s):dist[s] = 0;while (some vertices are unmarked) {v = unmarked vertex with smallest dist;Mark v;for (each w adj to v) {dist[w] = min[ dist[w], dist[v] + c(v,w) ];}}12Dijkstra’s Algorithm using Adj List■ Looks like we need a PQ● Problem: priorities are updated as algorithm runs● Can insert pair (v,dist[v]) in PQ whenever dist[v] is updated● At most e things in PQ■ Time O(v + e log e)■ Using a more complicated PQ (e.g., Pairing Heap), time can be brought down to O(e + v log v)● s is the start vertex● c(i,j) is the cost from i to j● Initially, vertices are unmarked● dist[v] is length of s-to-v path● Initially, dist[v] = ∞, for all vdijsktra(s):dist[s] = 0;while (some vertices are unmarked) {v = unmarked vertex with smallest dist;Mark v;for (each w adj to v) {dist[w] = min[ dist[w], dist[v] + c(v,w)
View Full Document
Unlocking...