第11讲(拓扑排序、最短路径)

数据结构 英文版 PPT

§2 Topological Sort〖Example〗 Courses needed for a computer science degree at a hypothetical universityCourse number C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C151/17

Course name Programming I Discrete Mathematics Data Structure Calculus I we convert this How shall Calculus II into a graph? Linear Algebra Analysis of Algorithms Assembly Language Operating Systems Programming Languages Compiler Design Artificial Intelligence Computational Theory Parallel Algorithms Numerical Analysis

Prerequisites None None C1, C2 None list C4 C5 C3, C6 C3 C7, C8 C7 C10 C7 C7 C13 C6

数据结构 英文版 PPT

§2 Topological Sort

AOV Network ::= digraph G in which V( G ) represents activities( e.g. the courses ) and E( G ) represents precedence relations ( e.g.C1 C3 means that C1 is a prerequisite course of C3 ).

i is a predecessor of j ::= there is a path from i to j i is an immediate predecessor of j ::= < i, j > E( G )Then j is called a successor ( immediate successor ) of i

Partial order ::= a precedence relation which is both transitive( i k, k j i j ) and irreflexive ( i i is impossible ).Note: If the precedence relation is reflexive, then there must be an i such that i is a predecessor of i. That is, i must be done before i is started. Therefore if a project is feasible, it must be irreflexive.

Feasible AOV network must be a DAG (directed acyclic graph).2/17

数据结构 英文版 PPT

§2 Topological Sort

【Definition】A topological order is a linear ordering of the vertices ofa graph such that, for any two vertices, i, j, if i is a predecessor of j in the network then i precedes j in the linear ordering.

〖Example〗 One possible suggestion on course schedule for acomputer science degree could be:Course number C1 C2 C4 C3 C5 C6 C7 C15 C8 C10 C9 C12 C13 C11 C14 Course name Programming I Discrete Mathematics Calculus I Data Structure Calculus II Linear Algebra Analysis of Algorithms Numerical Analysis Assembly Language Programming Languages Operating Systems Artificial Intelligence Computational Theory Compiler Design Parallel Algorithms Prerequisites None None None C1, C2 C4 C5 C3, C6 C6 C3 C7 C7, C8 C7 C7 C10 C13

3/17

数据结构 英文版 PPT

§2 Topological Sort

Note: The topological orders may not be unique for a network. For example, there are several ways (topological orders) to meet the degree requirements in computer science. Test an AOV for feasibility, and generate a topological order if possible.

Goal

void Topsort( Graph G ) { int Counter; p.337 9.1 Vertex V, W; Find a topological ordering for ( Counter = 0; Counter < NumVertex; Counter ++ ) { V = FindNewVertexOfDegreeZero( ); /* O( |V| ) */ if ( V == NotAVertex ) { Error ( “Graph has a cycle” ); break; } TopNum[V] = Counter; /*or output V */ for ( each W adjacent to V ) Indegree[ W ] – – ; } T = O( |V|2 ) }

Exercise:

4/17

数据结构 英文版 PPT

§2 Topological Sort

Improvement: Keep all the unassigned vertices of degree 0 in a specialbox (queue or stack).void Topsort( Graph G ) T = O( |V| + |E| )

{ Queue Q; int Counter = 0; Vertex V, W; Q = CreateQueue( NumVertex ); MakeEmpty( Q ); for ( each vertex V ) if ( Indegree[ V ] == 0 ) Enqueue( p.337 9.2 V, Q ); while ( !IsEmpty( Q ) ) { What V = Dequeue( Q );if a stack is used TopNum[ V ]instead = ++ Counter; assign next */ of a/*queue? for ( each W adjacent to V ) if ( – – Indegree[ W ] == 0 ) Enqueue( W, Q ); } /* end-while */ if ( Counter != NumVertex ) Error( “Graph has a cycle” ); DisposeQueue( Q ); /* free memory */ } Mistakes in Fig 9.4 on p.287v1 v3 v4 v2 v5

v6Indegree v1 v2 v3 v4 v5 v6 v7

v7v6

Home work:

0 1 0 2 1 0 3 1 2 0 1 0 3 2 1 0 2 1 0

v7v3 v4 v5 v2 v1

5/17

数据结构 英文版 PPT

§3 Shortest Path AlgorithmsGiven a digraph G = ( V, E ), and a cost function c( e ) for e E( G ). The length of a path P from source to destination is c(ei ) (also called weighted path length).ei P

1. Single-Source Shortest-Path Problem Given as input a weighted graph, G = ( V, E ), and a distinguished vertex, s, find the shortest weighted path from s to every other vertex in G.4

v12 5 8

2 1 3

v22 4

10

4

v12 5 8

2 1 3

v22 4

–10

Negative-cost cycle Note: If there is no

v3

v41

v56

v3

v41

v56

v6

v7

v6

v7

negative-cost cycle, the shortest path from s to s is defined to be zero.

6/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms

Unweighted Shortest Paths Sketch of the idea1 v 1 0 v3 1 v6

v2 2 v42

0: v3v53

1: v1 and v62: v2 and v4 3: v5 and v7

Breadth-first search

v7 3

ImplementationTable[ i ].Dist ::= distance from s to vi /* initialized to be except for s */ Table[ i ].Known ::= 1 if vi is checked; or 0 if not Table[ i ].Path ::= for tracking the path /* initialized to be 0 */

7/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms void Unweighted( Table T ) { int CurrDist; Vertex V, W; for ( CurrDist = 0; CurrDist < NumVertex; CurrDist ++ ) { for ( each vertex V ) if ( !T[ V ].Known && T[ V ].Dist == CurrDist ) { T[ V ].Known = true; for ( each W adjacent to V ) If V is unknown if ( T[ W ].Dist == Infinity ) { yet has Dist < T[ W ].Dist = CurrDist + 1; Infinity, then Dist T[ W ].Path = V; is either CurrDist } /* end-if Dist == Infinity */ } /* end-if !Known && Dist == CurrDist */ or CurrDist+1. } /* end-for CurrDist */ } 2

T = O( |V|v6 v5

)

The worst case:

v9

v8

v7

v4

v3

v2

v1

8/17

数据结构 英文版 PPT

Improvement

§3 Shortest Path Algorithms1 v10 v3 2 v6 1Dist Path

void Unweighted( Table T ) { /* T is initialized with the source vertex S given */ Queue Q; Vertex V, W; Q = CreateQueue (NumVertex ); MakeEmpty( Q ); Enqueue( S, Q ); /* Enqueue the source vertex */ while ( !IsEmpty( Q ) ) { V = Dequeue( Q ); T[ V ].Known = true; /* not really necessary */ for ( each W adjacent to V ) if ( T[ W ].Dist == Infinity ) { T[ W ].Dist = T[ V ].Dist + 1; T[ W ].Path = V; Enqueue( W, Q ); } /* end-if Dist == Infinity */ } /* end-while */ DisposeQueue( Q ); /* free memory */ }

2 v2v4 v7 3 v5 3

v1 v2 v3 v4 v5 v6 v7

1 v 0 3 2 v 0 1 0 2 3

1 3 0 v 0 1 v 0 2 v 0 3 v 0 4

v7 v5 v4 v2

v6v1 3

T = O( |V| + |E| )

9/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms

Dijkstra’s Algorithm (for weighted shortest paths) Let S = { s and vi’s whose shortest paths have been found } For any u S, define distance [ u ] = minimal length of path { s ( vi S ) u }. If the paths are generated in non-decreasing order, then the shortest path must go through ONLY vi S ;

u is chosen so that distance[ u ] = min{ w S | distance[ w ] } (If u is not unique, then we may select Why? If it is not true, then any of them) Greedy Method */ there must be;a /* vertex w on this path if distance [ unot distance [ u2... ] and we add u1 into S, 1 ] < in that is S. Then then distance [ u2 ] may change. If so, a shorter path from s to u2 must go through u1 and distance’ [ u2 ] = distance [ u1 ] + length(< u1, u2>).

10/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms void Dijkstra( Table T ) { /* T is initialized by Figure 9.30 on p.303 */ Vertex V, W; for ( ; ; ) { /* O( |V| ) */ V = smallest unknown distance vertex; if ( V == NotAVertex ) break; T[ V ].Known = true; for ( each W adjacent to V ) if ( !T[ W ].Known ) if ( T[ V ].Dist + Cvw < T[ W ].Dist ) { Decrease( T[ W ].Dist to T[ V ].Dist + Cvw ); T[ W ].Path = V; } /* end-if update W */ } /* end-for( ; ; ) */ } /* not work for edge with negative cost */4

v12 5 8

2 1 3

v22 4

10

v3

v41

v56

v6 v1 v2 v3 v4

v7

Dist Path 0 0 2 v 0 1 3 v 0 4 1 v 0 1 0 3 v 4 0 9 v 8 6 4 3 7 0 5 v 4

v5v6 v7

Please read Figure 9.31 on p.304 for printing the path.11/17

数据结构 英文版 PPT

Implementation 1V = smallest unknown distance vertex; /* simply scan the table – O( |V| ) */

§3 Shortest Path Algorithms

T = O( |V|2 + |E| )

Good if the graph is dense

Implementation 2V = smallest unknown distance vertex; /* keep distances in a priority queue and call DeleteMin – O( log|V| ) */

Home work:

p.339 9.5 Decrease( T[ W ].Dist to T[ V ].Dist + Cvw ); Find the shortest paths /* Method 1: DecreaseKey – O(9.10 log|V| ) */ p.340 T = O( |V| log|V| + |E|Dijkstra’s log|V| ) = O( algorithm |E| log|V| ) Modify

Good if the graph is sparse

/* Method 2: insert W with updated Dist into the priority queue */

/* Must keep doing DeleteMin until an unknown vertex emerges */

T = O( |E| log|V| ) but requires |E| DeleteMin with |E| space

Other improvements: Pairing heap (Ch.12) and Fibonacci heap (Ch. 11)12/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms

Graphs with Negative Edge Costsvoid WeightedNegative( Table T ) T = O( |V| |E| ) { /* T Too is initialized by Figure 9.30 on p.303 */ simple, and naïve… Hey I have a good idea: Queue Q; Try this one out: why don’t we simply add a constant Vertex V, W; 2 to edge and thus Q = CreateQueue (NumVertex ); MakeEmpty( Q remove ); 1 2 each negative edges? Enqueue( S, Q ); /* Enqueue the source vertex */ –2 1 3 Q ) ) { 4/* each vertex can dequeue at most |V| while ( !IsEmpty( 2 times */ V =

Dequeue( Q ); for ( each W adjacent to V ) if ( T[ V ].Dist + Cvw < T[ W ].Dist ) { /* no longer once T[ W ].Dist = T[ V ].Dist + Cvw; per edge */ T[ W ].Path = V; if ( W is not already in Q ) Enqueue( W, Q ); } /* end-if update */ } /* end-while */ DisposeQueue( Q ); /* free memory */ } /* negative-cost cycle will cause indefinite loop */

13/17

数据结构 英文版 PPT

Acyclic Graphs

§3 Shortest Path Algorithms

If the graph is acyclic, vertices may be selected in topological order since when a vertex is selected, its distance can no longer be lowered without any incoming edges from unknown nodes. T = O( |E| + |V| ) and no priority queue is needed.

Application: AOE ( Activity On Edge ) Networks—— scheduling a project

ai ::= activity

vj

Signals the completion of aiIndex of vertexEC TimeSlack Time

EC[ j ] \ LC[ j ] ::= the earliest \ latest completion time for node vj CPM ( Critical Path Method )

Lasting Time LC Time

14/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms

〖Example〗 AOE network of a hypothetical project 16 a0=6 1 6 a3=1 a6=9 a9=2 6 16 0 6 start 0 7 0 a1=4 4 7 a7=7 a10=4 8 a4=1 2 4 14 2 6 7 14 2 a2=5 a11=0 5 3 5a8=4 a5=2

18 18

finish

7 5 7( v , w ) E

3

Dummy activity

Calculation of EC: Start from v0, for any ai = <v, w>, we have

EC [ w ] max { EC [v ] C v , w }

Calculation of LC: Start from the last vertex v8, for any ai = <v, w>, we have LC [v ] min { LC [ w ] C v , w }( v , w ) E

Slack Time of <v,w> = LC[w] EC[v] Cv ,w

Critical Path ::= path consisting entirely of zero-slack edges.15/17

数据结构 英文版 PPT

§3 Shortest Path Algorithms

2. All-Pairs Shortest Path ProblemFor all pairs of vi and vj ( i j ), find the shortest path between.Method 1 Use single-source algorithm for |V| times.

T = O( |V|3 ) – works fast on sparse graph.Method 2 O( |V|3 ) algorithm given in Ch.10, works

faster on dense graphs.

16/17