第07章加权图WeightedGrahs

1、weighted graphs1weighted graphscbaedf032858487125239weighted graphs2outline and readingwweighted graphs (7.1)wdijkstras algorithm (7.1.1)wthe bellman-ford algorithm (7.1.2)wshortest paths in dags (7.1.3)wall-pairs shortest paths (7.2.1)wshortest path via matrix multiplication (7.2.2) no slide on thi

2、s section- too mathematical for slides!wminimum spanning trees (7.3)wthe prim-jarnik algorithm (7.3.2)wkruskals algorithm (7.3.1)wbaruvkas algorithm (7.3.3)weighted graphs3weighted graphswin a weighted graph, each edge has an associated numerical value, called the weight of the edgewedge weights may

3、 represent, distances, costs, etc.wexample:nin a flight route graph, the weight of an edge represents the distance in miles between the endpoint airportsordpvdmiadfwsfolaxlgahnl84980213871743184310991120123333725551421205weighted graphs4shortest path problemwgiven a weighted graph and two vertices u

4、 and v, we want to find a path of minimum total weight between u and v.nlength of a path is the sum of the weights of its edges.wexample:nshortest path between providence and honoluluwapplicationsninternet packet routing nflight reservationsndriving directionsordpvdmiadfwsfolaxlgahnl8498021387174318

5、4310991120123333725551421205weighted graphs5shortest path propertiesproperty 1:a subpath of a shortest path is itself a shortest pathproperty 2:there is a tree of shortest paths from a start vertex to all the other verticesexample:tree of shortest paths from providenceordpvdmiadfwsfolaxlgahnl8498021

6、3871743184310991120123333725551421205weighted graphs6dijkstras algorithmwthe distance of a vertex v from a vertex s is the length of a shortest path between s and vwdijkstras algorithm computes the distances of all the vertices from a given start vertex swassumptions:nthe graph is connectednthe edge

7、s are undirectednthe edge weights are nonnegativewwe grow a “cloud” of vertices, beginning with s and eventually covering all the verticeswwe store with each vertex v a label d(v) representing the distance of v from s in the subgraph consisting of the cloud and its adjacent verticeswat each stepnwe

8、add to the cloud the vertex u outside the cloud with the smallest distance label, d(u)nwe update the labels of the vertices adjacent to u weighted graphs7edge relaxationwconsider an edge e = = (u,z) such thatnu is the vertex most recently added to the cloudnz is not in the cloudwthe relaxation of ed

9、ge e updates distance d(z) as follows:d(z) mind(z),d(u) + weight(e)d(z) = 75 d(u) = 5010zsud(z) = 60 d(u) = 5010zsueeweighted graphs8examplecbaedf0428 487125239cbaedf0328511487125239cbaedf032858487125239cbaedf032758487125239weighted graphs9example (cont.)cbaedf032758487125239cbaedf032758487125239wei

10、ghted graphs10dijkstras algorithmwa priority queue stores the vertices outside the cloudnkey: distancenelement: vertexwlocator-based methodsninsert(k,e) returns a locator nreplacekey(l,k) changes the key of an itemwwe store two labels with each vertex:ndistance (d(v) label)nlocator in priority queue

11、algorithm dijkstradistances(g, s)q new heap-based priority queuefor all v g.vertices()if v = ssetdistance(v, 0)else setdistance(v, )l q.insert(getdistance(v), v)setlocator(v,l)while q.isempty()u q.removemin() for all e g.incidentedges(u) relax edge e z g.opposite(u,e)r getdistance(u) + weight(e)if r

12、 getdistance(z)setdistance(z,r) q.replacekey(getlocator(z),r)weighted graphs11analysiswgraph operationsnmethod incidentedges is called once for each vertexwlabel operationsnwe set/get the distance and locator labels of vertex z o(deg(z) timesnsetting/getting a label takes o(1) timewpriority queue op

13、erationsneach vertex is inserted once into and removed once from the priority queue, where each insertion or removal takes o(log n) timenthe key of a vertex in the priority queue is modified at most deg(w) times, where each key change takes o(log n) time wdijkstras algorithm runs in o(n + m) log n)

14、time provided the graph is represented by the adjacency list structurenrecall that s sv deg(v) = 2mwthe running time can also be expressed as o(m log n) since the graph is connectedweighted graphs12extensionwusing the template method pattern, we can extend dijkstras algorithm to return a tree of sho

15、rtest paths from the start vertex to all other verticeswwe store with each vertex a third label:nparent edge in the shortest path treewin the edge relaxation step, we update the parent labelalgorithm dijkstrashortestpathstree(g, s)for all v g.vertices()setparent(v, )for all e g.incidentedges(u) rela

16、x edge e z g.opposite(u,e)r getdistance(u) + weight(e)if r d(d), fs distance cannot be wrong. that is, there is no wrong vertex.weighted graphs14why it doesnt work for negative-weight edgesnif a node with a negative incident edge were to be added late to the cloud, it could mess up distances for ver

17、tices already in the cloud. cbaedf04575948712560-8dijkstras algorithm is based on the greedy method. it adds vertices by increasing distance.cs true distance is 1, but it is already in the cloud with d(c)=5!weighted graphs15bellman-ford algorithmwworks even with negative-weight edgeswmust assume dir

18、ected edges (for otherwise we would have negative-weight cycles)witeration i finds all shortest paths that use i edges.wrunning time: o(nm).wcan be extended to detect a negative-weight cycle if it exists nhow?algorithm bellmanford(g, s)for all v g.vertices()if v = ssetdistance(v, 0)else setdistance(

19、v, )for i 1 to n-1 dofor each e g.edges() relax edge e u g.origin(e)z g.opposite(u,e)r getdistance(u) + weight(e)if r getdistance(z)setdistance(z,r)weighted graphs16 -2bellman-ford example 0 4871-25-239 0 4871-2539nodes are labeled with their d(v) values-2-2804 4871-2539 8-24-15619-2501-194871-25-23

20、94weighted graphs17dag-based algorithmwworks even with negative-weight edgeswuses topological orderwdoesnt use any fancy data structureswis much faster than dijkstras algorithmwrunning time: o(n+m).algorithm dagdistances(g, s)for all v g.vertices()if v = ssetdistance(v, 0)else setdistance(v, )perfor

21、m a topological sort of the verticesfor u 1 to n do in topological orderfor each e g.outedges(u) relax edge e z g.opposite(u,e)r getdistance(u) + weight(e)if r weight(e) we can get a spanning tree of smaller weight by replacing e with f842367798ecf842367798cefreplacing f with e yieldsa better spanni

22、ng tree weighted graphs23uvpartition propertypartition property:nconsider a partition of the vertices of g into subsets u and vnlet e be an edge of minimum weight across the partitionnthere is a minimum spanning tree of g containing edge eproof:nlet t be an mst of gnif t does not contain e, consider

23、 the cycle c formed by e with t and let f be an edge of c across the partitionnby the cycle property,weight(f) weight(e) nthus, weight(f) = = weight(e)nwe obtain another mst by replacing f with e742857398ef742857398efreplacing f with e yieldsanother mstuvweighted graphs24prim-jarniks algorithmwsimil

24、ar to dijkstras algorithm (for a connected graph)wwe pick an arbitrary vertex s and we grow the mst as a cloud of vertices, starting from swwe store with each vertex v a label d(v) = the smallest weight of an edge connecting v to a vertex in the cloud at each step:n we add to the cloud the vertex u

25、outside the cloud with the smallest distance labeln we update the labels of the vertices adjacent to u weighted graphs25prim-jarniks algorithm (cont.)wa priority queue stores the vertices outside the cloudnkey: distancenelement: vertexwlocator-based methodsninsert(k,e) returns a locator nreplacekey(

26、l,k) changes the key of an itemwwe store three labels with each vertex:ndistancenparent edge in mstnlocator in priority queuealgorithm primjarnikmst(g)q new heap-based priority queues a vertex of gfor all v g.vertices()if v = ssetdistance(v, 0)else setdistance(v, )setparent(v, )l q.insert(getdistanc

27、e(v), v)setlocator(v,l)while q.isempty()u q.removemin() for all e g.incidentedges(u)z g.opposite(u,e)r weight(e)if r getdistance(z)setdistance(z,r)setparent(z,e) q.replacekey(getlocator(z),r)weighted graphs26examplebdcafe7428573980728 bdcafe7428573980725 7bdcafe7428573980725 7bdcafe742857398072547we

28、ighted graphs27example (contd.)bdcafe742857398032547bdcafe742857398032547weighted graphs28analysiswgraph operationsnmethod incidentedges is called once for each vertexwlabel operationsnwe set/get the distance, parent and locator labels of vertex z o(deg(z) timesnsetting/getting a label takes o(1) ti

29、mewpriority queue operationsneach vertex is inserted once into and removed once from the priority queue, where each insertion or removal takes o(log n) timenthe key of a vertex w in the priority queue is modified at most deg(w) times, where each key change takes o(log n) time wprim-jarniks algorithm

30、 runs in o(n + m) log n) time provided the graph is represented by the adjacency list structurenrecall that s sv deg(v) = 2mwthe running time is o(m log n) since the graph is connectedweighted graphs29kruskals algorithma priority queue stores the edges outside the cloudnkey: weightnelement: edgeat t

31、he end of the algorithmnwe are left with one cloud that encompasses the mstna tree t which is our mstalgorithm kruskalmst(g)for each vertex v in g dodefine a cloud(v) of vlet q be a priority queue.insert all edges into q using their weights as the keyt while t has fewer than n-1 edges doedge e = t.r

32、emovemin()let u, v be the endpoints of eif cloud(v) cloud(u) thenadd edge e to tmerge cloud(v) and cloud(u)return tweighted graphs30data structure for kruskal algortihmwthe algorithm maintains a forest of treeswan edge is accepted it if connects distinct treeswwe need a data structure that maintains

33、 a partition, i.e., a collection of disjoint sets, with the operations: -find(u): return the set storing u -union(u,v): replace the sets storing u and v with their unionweighted graphs31representation of a partitionweach set is stored in a sequenceweach element has a reference back to the setnoperat

34、ion find(u) takes o(1) time, and returns the set of which u is a member.nin operation union(u,v), we move the elements of the smaller set to the sequence of the larger set and update their referencesnthe time for operation union(u,v) is min(nu,nv), where nu and nv are the sizes of the sets storing u

35、 and vwwhenever an element is processed, it goes into a set of size at least double, hence each element is processed at most log n timesweighted graphs32partition-based implementationwa partition-based version of kruskals algorithm performs cloud merges as unions and tests as finds.algorithm kruskal

36、(g): input: a weighted graph g. output: an mst t for g.let p be a partition of the vertices of g, where each vertex forms a separate set.let q be a priority queue storing the edges of g, sorted by their weightslet t be an initially-empty treewhile q is not empty do (u,v) q.removeminelement() if p.fi

37、nd(u) != p.find(v) thenadd (u,v) to tp.union(u,v)return trunning time: o(n+m)log n)weighted graphs33kruskal examplejfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391184946109011212342184662180214641235337weighted graphs34jfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391184946109011212342184

38、662180214641235337exampleweighted graphs35examplejfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391184946109011212342184662180214641235337weighted graphs36examplejfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391184946109011212342184662180214641235337weighted graphs37examplejfkbosmiaordlaxdf

39、wsfobwipvd867270418712588491447401391184946109011212342184662180214641235337weighted graphs38examplejfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391184946109011212342184662180214641235337weighted graphs39examplejfkbosmiaordlaxdfwsfobwipvd86727041871258849144740139118494610901121234218466218021

40、4641235337weighted graphs40examplejfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391184946109011212342184662180214641235337weighted graphs41examplejfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391184946109011212342184662180214641235337weighted graphs42examplejfkbosmiaordlaxdfwsfobwipvd867270418712588491447401391