复旦大学：《数据结构与算法设计》实验设计_Lab 7. Single-Source Shortest Paths

Lab 7 Single-Source Shortest Paths The Program(or Project) Evaluation and Review Technique, commonly abbreviated PERT, is a statistical tool, used in project management, that is designed to analyze and represent the tasks involved in completing a given project. First developed by the United States Navy in the 1950s,it is commonly used in conjunction with the critical path method or CPM An interesting application of the single-source shortest path algorithms arises in determining critical paths in PERT chart analysis. Edges represent jobs to be performed, and edge weights epresent the times required to perform particular jobs If edge(u, v)enters vertex v and edge(v, x) en job(u, v)must be perform (v, x). A path through this dag re sequence of jobs that must be performed in a particular order. a critical path is a longest path ough the dag, corresponding to the longest time to perfo The Pert chart formulation given above is somewhat unnatural. It would be more natural for vertices to represent jobs and edges to represent sequencing constraints; that is, edge(u, v) would indicate that job u must be performed before job v, weights would then be assigned to vertices, not edges. Write a procedure that can finds a longest path in a directed acyclic graph with weighted ertices in l (1)Algorithm and implemented code(including three use cases)(60% (2)Efficiency of the algorithm(20%) (3)Document(20%) History Program Evaluation and Review Technique The Navys Special Projects Office, charged with developing the Polaris-Submanine weapon system and the Fleet Ballistic Missile capability, has developed a statistical technique for measuring and forecasting progress in research and development programs. This Program Evaluation and Review Technique (code-named PERT) is applied as a decision-making tool designe to save time in achieving end-objectives, and is of particular interest to those engaged in research and development programs for which time is a critical factor The new technique takes recognition of three factors that influence ul achievement of research and development program objectives time, resources, and technical performance specifications. PERT employs time as the variable that reflects planned resource-applications and performance specifications. with units of time as a common denominator, PERT quantifies knowledge about the uncertainties involved in developmental programs requiring effort at the edge of, or beyond. current knowledge of the subject-effort for which litie or no previous experience exists Through an electronic computer, the peRt technique processes data representing the major, finite accomplishments (events)essential to achieve end-objectives the inter-dependence of those events and estimates of time and range of time necessary to complete each activity between two successive events. Such time expectations include estimates of " most like time,optimistic time, and pessimistic time" for each activity. The technique is a management control tool that sizes up the outlook for meeting objectives on time highlights danger signals requiring management decisions reveals and defines both criticalness and slack in the flow plan or the network of sequential activities that must be performed to meet objectives compares current expectations with scheduled completion dates and computes the probability for meeting so and simulates the effects of options for decision- before decision The concept of PERT was developed by an operations research team staffed with representatives from the Operations Research Department of Booz Allen and Hamilton; the Evaluation Office of the Lockheed Missile Systems Division; and Program Evaluation Branch, Special Projects Office, of the Department of the Navy. -Willard Fazar(Head, Program Evaluation Branch, Special Projects Office, U. S Navy). The American Statistician, April 1959

Lab 7 Single-Source Shortest Paths. The Program (or Project) Evaluation and Review Technique, commonly abbreviated PERT, is a statistical tool, used in project management, that is designed to analyze and represent the tasks involved in completing a given project. First developed by the United States Navy in the 1950s, it is commonly used in conjunction with the critical path method or CPM. An interesting application of the single-source shortest path algorithms arises in determining critical paths in PERT chart analysis. Edges represent jobs to be performed, and edge weights represent the times required to perform particular jobs. If edge (u, v) enters vertex v and edge (v, x) leaves v, then job (u, v) must be performed prior to job (v, x). A path through this dag represents a sequence of jobs that must be performed in a particular order. A critical path is a longest path through the dag, corresponding to the longest time to perform an ordered sequence of jobs. The PERT chart formulation given above is somewhat unnatural. It would be more natural for vertices to represent jobs and edges to represent sequencing constraints; that is, edge (u, v) would indicate that job u must be performed before job v. weights would then be assigned to vertices, not edges. Write a procedure that can finds a longest path in a directed acyclic graph with weighted vertices in linear time. Grading (1) Algorithm and implemented code (including three use cases) (60%). (2) Efficiency of the algorithm (20%). (3) Document (20%). History