Transcript 没有幻灯片标题
§2 Topological Sort
〖Example〗 Courses needed for a computer science
degree at a hypothetical university
Course number
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
C13
C14
C15
1/17
Course name
Programming I
Discrete Mathematics
Data Structure
Calculus
How
shallI we convert this
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
§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
§2 Topological Sort
【Definition】A topological order is a linear ordering of the vertices of
a 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 a
computer science degree could be:
Course number
C1
C2
C4
C3
C5
C6
C7
C15
C8
C10
C9
C12
C13
C11
C14
3/17
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
§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.
Goal
Test an AOV for feasibility, and generate a topological
order if possible.
void Topsort( Graph G )
{ int Counter;
Vertex V, W;
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 )
}
4/17
§2 Topological Sort
Improvement: Keep all the unassigned vertices of degree 0 in a special
box (queue or stack).
Mistakes in Fig 9.4 on
p.289
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.339
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 */
}
Home work:
5/17
v1
v2
v3
v4
v6
Indegree
v1
v2
v3
v4
v5
v6
v7
0
01
2
1
0
0213
01
3
1
02
012
v5
v7
v6
v7
v3
v4
v5
v2
v1
§3 Shortest Path Algorithms
Given 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.
2
v1
4
1
2
v3
5
8
v6
6/17
3
v4
1
v2
10
2
4
v5
6
v7
2
v1
4
1
3
2
v3
5
v2
8
v6
v4
1
–10
2
4
v5
6
v7
Negative-cost
Note: Ifcycle
there is no
negative-cost cycle,
the shortest path
from s to s is
defined to be zero.
§3 Shortest Path Algorithms
Unweighted Shortest Paths
Sketch of the idea
1 v
1
0 v3
v4
1 v6
0: v3
v2 2
2
v5
v7 3
3
1: v1 and v6
2: v2 and v4
Breadth-first
search
3: v5 and v7
Implementation
Table[ 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
§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|
The worst case:
8/17
v9
v8
v7
v6
v5
)
v4
v3
v2
v1
Improvement
§3 Shortest Path Algorithms
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 */
}
9/17
1
v1
0
2
v2
2
v3
3
v4
v6
1
v5
v7
3
Dist Path
v1
v2
v3
v4
v5
v6
v7
1 v03
2 v01
0
2
3
1
3
0
v01
v02
v03
v04
v7
v5
v4
v2
v6
v13
T = O( |V| + |E| )
§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{ wS |
distance[ w ] } (If u is not unique, then we may select
Why? If it is not true, then
any ofmust
them)
Greedy Method */
there
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
§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 */
2
v1
4
1
2
v3
8
5
v4
10
2
4
1
v6
v7
v1
0
v2
2 v01
v3
3 v04
v4
1 v01
v5
3 v04
v6
9 v0734
8
6
v7
5 v04
0
v5
6
Dist Path
Please read Figure 9.31 on p.304 for printing the path.
11/17
v2
3
§3 Shortest Path Algorithms
Implementation 1
V = smallest unknown distance vertex;
/* simply scan the table – O( |V| ) */
T = O( |V|2 + |E| )
Good if the graph is dense
Implementation 2
Home work:
V = smallest unknown distance vertex;
/* keep distances in a priority queue and call DeleteMin – O( log|V| ) */
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
§3 Shortest Path Algorithms
Graphs with Negative Edge Costs
void 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,– 2Q ); /* Enqueue the
source
vertex */
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
§3 Shortest Path Algorithms
Acyclic Graphs
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 ai
EC[ j ] \ LC[ j ] ::= the earliest \
latest completion time for node vj
CPM ( Critical Path Method )
Index of vertex
EC Time
Lasting Time
Slack Time
14/17
LC Time
§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
18
18
finish
a8=4
5
3 5
a5=2
7
5 7
3
Dummy activity
Calculation of EC: Start from v0, for any ai = <v, w>, we have
EC [ w ] max { EC [v ] C v , w }
( v , w )E
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
§3 Shortest Path Algorithms
2. All-Pairs Shortest Path Problem
For 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
§3 Shortest Path Algorithms
Laboratory Project 5
Saving James Bond
Due: Thursday, December 7th, 2006 at 10:00pm
Detailed requirements can be downloaded from
http://10.71.45.99/list.asp?boardid=47
Courseware Download
Don’t forget to sign
you names
and duties at the end of
your report.
17/17