案例數(shù)據(jù)結(jié)構(gòu)-計

1、4 Shortest Paths ParisBrusselsBernMunichPragueVienna34618356619428550440727194311461542902Edsger Wybe Dijkstra (19302002)tsxr wib dkstraDijkstras algorithm Paris(巴黎)Brussels(比利時布魯塞爾)Bern(瑞士泊爾尼)Munich(慕尼黑)Prague(捷克布拉格)Vienna(維也納)346183566194285504407271001833461833460679749679749183183617346346346617

2、617904904617749749904904904Shortest Paths ProblemGiven a digraph G = ( V, E ), and a weighting function w( e ) 0 for e E( G ). The length of a path P from source to destination is 1. Single Source All DestinationsGiven a source v0. Determine a shortest path to each v V(G) v0 .Note: A path with minim

3、al number of vertices is NOT necessarily the shortest.v0v1v3v4v2v52010501515201035303453) v0 v3 v4 v12) v0 v3 v44) v0 v21) v0 v3PathLength10254545non-decreasing4 Shortest PathsLet S = v0 and vis whose shortest paths have been found For any u S, define distance u = minimal length of path v0 ( vi S )

4、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 any of them) ; /* Greedy Method */ if distance u1 distance u2 and we add u1 into S, then distance u2

5、 may change. If so, a shorter path from v0 to u2 must go through u1 and distance u2 = distance u1 + length().Implementation vi = 0, 1, ., n1 Note: LARGE_NO must be greater than maxw(ei), and maxdistancei +LARGE_NO wont overflow.4 Shortest Pathsvoid shortestpath ( int v, int cost MAX_VERTICES , int d

6、istance , int n, short int found ) int i, u, w ; for ( i = 0; i n; i+ ) /* initialization */ found i = FALSE ; distance i = cost v i ; /* end for-loop */ found v = TRUE ; distance v = 0 ; for ( i = 0; i n2; i+ ) u = choose ( distance, n, found ) ; /* O( n ) */ /* find the min distance not yet checke

7、d. */ found u = TRUE ; for ( w = 0; w n; w+ ) if ( !found w ) if ( distance u + cost u w distance w ) /* if adding u into S makes distancew shorter */ distance w = distance u + cost u w ; /* end for-loop */Tp = O( n2 )4 Shortest Pathsint choose(int distance, int n, short int found) int i, min, minpo

8、s; min = INT_MAX; minpos = -1; for(i=0; in; i+) if(distancei min & FALSE = foundi) min = distancei;minpos = i; return minpos;5 Activity Networks1. Activity On Vertex ( AOV ) NetworksExample Courses needed for a computer science degree at a hypothetical universityHow shall we convert this list into a

9、 graph?5 Activity Networks AOV Network := digraph G in which V( G ) represents activities ( e.g. the courses ) and E( G ) represents precedence relations(先序關(guān)系) ( e.g. means that C1 is a prerequisite(先修) course of C3 ).C1C3 i is a predecessor of j := there is a path from i to j i is an immediate pred

10、ecessor of 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

11、 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).5 Activity Networks【Definition】A topological order is a linear ordering of the vertices of a graph such that, for a

12、ny two vertices, i, j, if i is a predecessor of j in the network then i precedes j in the linear ordering.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.GoalTest an AOV for feasibility, and generate a topological order if possible.Algorithmfor ( i = 0; i n; i+ ) if ever