有向图的关键路径毕业论文

关键概念定义

AOV网 ：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，就是AOV网。

关键路径算法原理 ：先求所有顶点的事件最早发生时间（从起点开始计算），如有顶点1和顶点2都到达顶点3，那么顶点3的最早开始时间为max(顶点1 + 路径长度，顶点2 + 路径长度)；之后求出所有顶点的时间最迟发生时间（从终点开始计算），如顶点3会到达顶点4和顶点5，那么顶点3的最迟发生时间为min（顶点4 - 路径长度，顶点5 - 路径长度)。比较事件最早发生时间数组和事件最迟发生时间数据，若是对应位置的值相等（即没有可延迟的时间），那么该顶点就是关键路径上的顶点。比较完所有顶点即可输出关键路径。

论文开题报告基本要素

各部分撰写内容

论文标题应该简洁，且能让读者对论文所研究的主题一目了然。

摘要是对论文提纲的总结，通常不超过1或2页，摘要包含以下内容：

目录应该列出所有带有页码的标题和副标题， 副标题应缩进。

这部分应该从宏观的角度来解释研究背景，缩小研究问题的范围，适当列出相关的参考文献。

这一部分不只是你已经阅读过的相关文献的总结摘要，而是必须对其进行批判性评论，并能够将这些文献与你提出的研究联系起来。

这部分应该告诉读者你想在研究中发现什么。在这部分明确地陈述你的研究问题和假设。在大多数情况下，主要研究问题应该足够广泛，而次要研究问题和假设则更具体，每个问题都应该侧重于研究的某个方面。

运用 毕业 生优秀论文汇总表分析,探索一条提高学生毕业论文写作水平和毕业论文管理工作水平的路径,为提高高校实践教学水平而努力。下面是我为大家推荐的优秀毕业论文，供大家参考。

优秀毕业论文 范文 一：与护理学专业本科毕业文指导的相关毕业论文

摘 要目的：研讨提高护理学本科学生毕业论文质量的 措施 . 方法 ：通过对本校近几年来对护理学专业毕业论文指导中关于选题,指导手段,答辨评价体系的 总结 ,探讨一系列行之有效的方法.结果：提高学生对毕业论文的重视度,合理的选题,优化指导模式能较大程度提高毕业论文的撰写质量.结论：提高护理学专业本科生的毕业论文质量的综合举措,对培养高素质创新型临床护理实践人才,提升护理服务能力和专业水平起着积极的作用.

关 键 词毕业论文本科护生选题论文答辩

中图分类号：G640文献标识码：A

ThinkingofNursingProfessionalUndergraduateThesisGuidance

WEIYoulong,ZHANGLirong

(MedicalandNursingSchool,ChengduUniversity,Chengdu,Sichuan610106)

AbstractPurpose：：Throughthesummaryofschoolinrecentyearsonthenursingprofessionthesisguidanceontopics,guidancetools,：Toimprovestudents'degreeofemphasisonthethesis,reasonabletopic,greaterdegreeofoptimizationguidancemo

：Toimprovenursingqualityundergraduatethesisintegratedinitiativesplaysanactiveroleforcultivatinghighqualityclinicalnursingpracticetalents,andimprovethelevelofcareandprofessional.

Keywordsundergraduatethesis;undergraduatenursingstudents;topic;thesis

1提高学生的重视程度是完成毕业论文的基础

本科新生进入学校后就应让学生明确毕业论文是本科生在大学学习阶段最重要的一门课程,是授予学位的必要条件,对其综合能力的培养和素质的提升起着重要的作用.用往届因毕业论文不合格而未拿到学位的例子,打消学生侥幸过关的心理,端正态度.同时指导教师在指导环节也应该以高度的责任感和事业心对待这项教学任务,并制定相应的奖惩制度.我校护理学本科学生有一年的实习期,在学生进入实习前的一学期成立本科毕业论文领导小组,组织毕业论文写作讲座,确定指导教师指导的学生名单.召开开题 报告 会,再次强调毕业论文的重要性及完成每一环节的时间安排.

2合理的选题是完成毕业论文的关键

选题是毕业论文的起点,合理的选题更是保证毕业论文质量的关键.毕业论文的选题要具有一定的理论意义和现实应用价值,要符合培养目标的要求,体现专业特色,选题应具有一定的深度、广度,选题应大小适宜,题目新颖.

从专业课程的学习中获取选题的灵感.虽然毕业论文一般在最后一年进行,但是学生在校专业课的学习中就应有所准备.专业课教师在授课时,应提出与本课内容相关的一些前沿知识及在护理学领域中对一些问题的不同观点,而这些知识、观点、问题都可能引起某些学生的高度关注,甚至成为他以后毕业论文的选题.

从大学生创新实验中进行总结归纳得到选题.我校每年进行的校级大学生创新性实验计划是我校开展以实验为主要手段的大学生自主管理的科技创新实验活动,为我校“质量工程”建设中一项以学生为主体的项目,其实施可激发学生的创新意识和 创新思维 ,锻炼学生的创新和实践能力.学生积极申请参与项目过程中,可以找到适合学生自己的毕业论文的选题.

从临床实习中发现问题上,提出论点.护理专业实习教学作为理论联系实践的过渡时期,是培养合格的护理人员必经的途径,我校护理学专业本科学生有一年完整的系统的综合医院的实习时间.学生在不同科室的实习中所接触到的新观念、新技术及发现的一些新问题等,学生可以把自已最感兴趣的方面作为毕业论文的选题.

从教师的科研项目中分出一些子项目作为毕业论文的选题,这是一个较好的方式,最好是参与科研项目的同学,但能参与教师科研项目的本科层次学生毕竟有限.

查阅文献,从中获取选题方向.阅读大量中英文综述、论文,先粗读,从中选取对论文选题及写作有参考价值的 文章 ;再进行精读,从中提取有意义的内容.有疑惑或困难时要向指导教师多请教;同学之间要多联系、探讨,获得同学的协助、支持.

3优化指导模式是完成毕业论文的重要手段

建立毕业论文辅导的群,便于加强教师与学生之间的联系.学生书写毕业论文主要是在实习期间,与指导教师当面交流的机会较少,建立毕业论文的专用群,可以及时将学校对毕业论文的通知和要求传到群共享中,并能与学生及时沟通,解决学生提出的各种问题.同学也可以将论文书写中出现的一些问题在群里进行讨论.标准化毕业论文格式,我们学校是一所综合性的院校,作为医学及护理学专业有其自身的特点,故此学院在大学论文格式的基础上作了一些修订,制定出更加适合护理学科的论文格式,让学生严格按照格式书写.

重视统计软件的学习及辅导,从最近几年护理学生在论文选题上看,有很大一部分是调查报告,这必然会涉及较多的数据分析和处理,故此应加强护理学生在校期间对统计学及统计软件应用能力的培养.

建立毕业论文数据库及优秀毕业论文展区,学生可以对历届优秀毕业论文进行学习、借鉴,推陈出新.

严格限定教师指导学生的数量才能保证论文的质量,一般学校都将教师指导学生的数量计为教学工作量,有些教师为了完成更多的工作量会导致辅导的学生过多.人的精力是有限的,辅导学生过多必然导致论文质量的下降.故此学校应根据教师的职称,平时的教学工作量及其指导的往届学生论文的质量等方面综合考虑,合理地安排其指导学生人数.

评阅老师严格把关,将学院毕业论文的指导教师进行分组,同组指导教师之间可以对其指导的论文进行交叉审阅,相互提出参考意见.并让 经验 丰富的指导教师同时担当该组的评阅教师,对开题报告及论文进行评阅把关,以保证毕业论文的整体质量.

重视英文摘 要的书写,毕业论文都要求学生书写相应的英文摘 要,有些英文底子较差的学生在英文摘 要的书写时常用些翻译软件,造成英文摘 要错误极多.指导教师要对此严格把关,不合格者不允许参与论文答辩,这样也可以促进学生平时加强对英文的学习.

重视毕业论文的答辩工作,严控质量关.毕业论文答辩分组进行,指导教师与其指导的学生应分配在不同的答辩组,完善答辩评分标准.学生毕业论文的成绩由三部分构成：一是指导教师评分,二是评阅教师评分,三是答辩成绩,三个成绩分别占不同的比例,最后计算出总评成绩.对不合格论文进行整改,整改后进行二次答辩,二次答辩不合格者缓授或不授予学位.对优秀论文获得的学生及指导教师进行相应表彰,并推荐一些优秀论文发表,增强学生的成就感.

总之,学校、教师及学生对毕业论文高度重视,严格把握本科护生对论文的选题,并应用科学的指导方法,规范答辩模式,合理评价标准,行之有效的奖罚制度,才能保证本科护生毕业论文的整体质量,提高护生素质.

*通讯作者：张莉蓉

参考文献

[1]陈振斌,张建珍.本科毕业论文(设计)选题情况调查与思考[J].海南大学学报自然科学版,2011.

[2]杨雷,齐静.医学护理专业毕业论文改革的研究与实践[J].卫生职业 教育 ,2011(22)：8-9.

[3]丁艳芳,齐涛.谈毕业论文质量下降的原因及应对措施[J].河北农业大学学报：农林教育版,2004(1)：12-14.

[4]钟卫东.加强毕业论文过程的指导,提高毕业论文的写作质量[J].高等教育,2011.

优秀毕业论文范文二：与提高环境工程专业毕业文(设计)质量的与实践相关毕业论文

本文是一篇环境工程论文范文,环境工程类有关毕业论文范文,关于提高环境工程专业毕业文(设计)质量的与实践相关大学毕业论文范文。适合环境工程及毕业论文及医学院方面的的大学硕士和本科毕业论文以及环境工程相关开题 报告范文 和职称论文写作参考文献资料下载。

基于对环境工程专业本科毕业论文(设计)存在的一些实际问题为前提,通过分析出现这些问题的原因及本专业的实际情况,我们认为应从毕业论文选题、指导教师队伍建设、解决毕业论文与求职 考研 的冲突、严格加强指导过程管理等方面入手,解决目前毕业论文工作中出现的问题,提高毕业论文质量.

环境工程毕业论文教学改革毕业论文是整个本科教育中最后一个环节,约占本科教学内容的1/8,作为架构学生从理论学习到实际工作岗位的桥梁,是对教学质量和办学水平的一次综合性全面考核.通过毕业论文的训练能够有效提高学生综合运用大学四年所学的所有理论知识与实验技能解决实际问题的能力,为以后实际工作打下坚实的基础.

泰山医学院是一所地方性本科院校,其环境工程专业主要培养应用型工程技术人才,培养的学生主要在环境管理与咨询、环保公司、化工企业、疾控中心等单位从事污染控制工程设计、环境监测与评价及技术研发等工作.通过对近三年来环境工程本科毕业论文的统计分析,发现在毕业设计题目、内容、写作质量、工作量和难易程度等方面存在一定问题,需要进一步改进和完善.正是基于这种情况的考量,环境工程专业对于毕业论文的培养模式提出了一些新的想法和思路,并的实践应用取得了一定的效果.

一、重视毕业论文选题

选题是毕业论文工作的龙头,选题质量是毕业论文质量的起点和关键.题目的质量将直接影响到毕业论文的质量.通过对近三年来毕业设计题目的统计分析,发现有约20%左右的论文题目存在雷同,论文内容缺乏创新性.造成这一现象的原因,与近几年环境工程专业人数较多,承担毕业论文指导任务的主要为环境工程教研室的教师,每个教师要指导4～8个毕业生,由于指导教师的精力有限,部分教师缺乏科研工作经历,造成多个学生做同一个题目,不同学生之间仅在实验地点、实验材料或监测项目等方面做稍微变化,缺乏创新性和对某个题目的深入研究,造成最后在确定毕业设计题目时存在雷同.另外,由于师资的限制,选题更新较慢,难以体现创新性内涵.

在发现这些问题的基础上,我们进行了一些有益的探索.在选题上尝试师生共同完成毕业论文题目的申报,因材施教.我们在专业基础课和专业课的教学过程中,鼓励教师与课程平行的进行实验室开放,引导学生进行一些专业相关课程的综合性、设计性实验的训练,并在这个过程中指导学生查阅一些专业文献,撰写综述,扩展学生的视野和知识面,充分调动学生的积极性和主动性.经过开放实验的训练,使学生对本专业的一些问题有了深入的理解和体会,并能够提出自己的一些想法和见解,激发了学生的学习兴趣.同时通过一个学期的开放实验指也会密切老师和学生的关系,老师能够了解到不同学生的个性差异和能力水平及各自的优势,因材施教,有的放矢地进行教学.在此基础上,在选题方式上,改变指导教师单方面指定题目的做法,鼓励学生根据参加开放实验积累的知识和经验在查阅文献资料的基础上,一部分学生会自主提出感兴趣的题目,以导师把关的方式,师生互动来选题,尽可能培养学生创造性思维活动的能力.

二、加强指导教师队伍建设

由于教研室师资有限,年轻教师多,职称结构不尽合理,经常出现一名讲师要指导多名本科毕业生的情况,在这种情况下,还要求学生一人一题,题目不能重复,从师资配备的角度考虑具有一定的难度.毕业论文的内容和大同小异的现象仍较为普遍,创新性内涵的体现几乎流于形式.

为提高环境工程专业毕业设计的质量,我们在校内和校外两个层面上筛选高水平的优质师资作为指导教师.一方面,鼓励考取研究生的学生到考取学校在导师的指导下从事毕业论文工作,既可以提高毕业论文质量,又可以为今后的研究生学习打下基础.另一方面,学院为找工作的学生联系实习单位,利用实习单位的高水平师资和实验条件来完成毕业论文.在校内,我们整合化工学院的其他一些优秀师资力量,聘请基础教研室具有博士学位和高级职称的教师作为毕业论文指导教师,使环境工程专业的毕业论文在选题范围、指导教师职称、学历及论文质量上都有了较大的提高.

三、解决毕业论文与求职考研的冲突

经过多年指导毕业论文的实践,我们发现,现在学生就业和考研压力非常大是导致毕业论文(设计)质量下降的最主要原因.由于目前学生的就业的压力较大,班级里大部分学生都选择了考研,在第七学期都全力以赴准备考研,在第八学期的3～4月份又是考研复试的主要时间,很多上线的学生又把主要的精力放在准备 面试 上,等到面试结束,真正开始进行毕业论文的实验已经为时过晚.由于考研对时间的占用导致学生将原本重要的毕业论文工作放在从属地位.因此不但毕业论文的质量会下降,没有经过毕业论文这个阶段的训练,学生的求职、考研面试也收到很大的影响.

因此,我们尝试将毕业论文工作提前,一般到第七学期初甚至第六学期开始让学生选题,并开始毕业论文的部分工作,如：文献检索,撰写综述等.在这方面也主要得益于开放实验项目的开展,如一部分在第五学期参加过环境微生物开放实验的同学在结束了一学期的综合实验后,对微生物治理环境污染物产生浓厚的兴趣,因此在第六学期继续进实验室作实验,经过一年多的试验收获很大,所以到第七学期个别优秀的学生在老师的指导下,能总结实验结果撰写科研论文并发表.

四、提高毕业论文写作质量,重视毕业论文答辩

答辩是整个毕业论文过程的一个重要环节,也是确定毕业论文总成绩的重要考评依据.针对以往毕业论文答辩过程中的诸多问题,如幻灯片字数多、字体小、颜色搭配不合理,答辩内容不熟悉,图标绘制不规范等,要求指导教师对本小组的学生进行预答辩,减少答辩时的常规错误.对于答辩过程中评委提出的相关问题,指导教师督促学生认证整改,提高论文质量.

参考文献：

\[1\]郑宇,张云.对本科生毕业论文写作能力培养的思考\[J\].中国林业教育,2008,(6)：11-13.

\[2\]陈云嫩,梁礼明.高校环境工程专业毕业设计(论文)与就业双赢之探讨\[J\].信息系统工程,2010,2(3)：135-137.

\[3\]张烈平.普通高校信息类专业毕业实习(设计)改革初探\[J\].高等理科教育,2006,(4)：90-92.

\[4\]张庆乐,董建,王虹,郑超.环境工程毕业设计存在的问题及对策研究\[J\].中国电力教育,2012,21(5)：66-68.

据学术堂了解撰写本科毕业论文的开题报告，一定不要急于下笔，首先要理清思路。理清思路的过程就是你报告的一个大纲，建议开题报告的模板进行思考，并查找相关资料。1.我的研究方向是什么？我为什么要进行这样的研究？（选题依据）2.这个研究方向有什么特殊的背景？（课题来源）3.我的研究想要得出的结论是什么？能够给我们带来哪些实际的意义？（研究目的和研究意义）4.关于这个方向，国内和国外已经做过哪些研究？有哪些成果？（研究现状）5.我的研究与前人的研究相比，有哪些进步的地方？（创新性分析）6.要完成我的开题报告，我还应该知道哪些相关知识？完成哪些工作（研究内容）7.要完成我的开题报告，我应该掌握哪些技术？（研究方法）8.有哪些主客观因素对我的研究有利？（可行性分析）9.在这个过程中我有可能遇到的挫折有哪些？我应该怎样克服这些障碍呢？这个思路基本上是沿着研究步骤进行的，理清这些问题，你才有可能写出一篇比较符合要求的开题报告，而且不会卡顿。做好这些前提工作，就可以进入撰写阶段了：1 选题背景及研究意义 选题背景选题背景就是对选题起作用的历史情况或现实环境。选题背景就是要说明作者是根据什么、受什么启发而对该选题进行研究。最好简单说明一下预期研究成果的现实指导意义。 研究意义选题的研究意义就是阐述为什么要研究、研究它有什么价值。意义=价值，包括现实价值和理论价值。首先要突出说明的是选题的现实价值，每一个研究的目的都是为了指导现实生活，一定要讲清本选题的研究有什么实际作用、解决什么问题；其次再写课题的理论和学术价值。不要牵扯太远，可从题目的关键字说起，要写得具体一点，有针对性一点，不能漫无边际地空喊口号。比如“房地产开发项目成本管理研究”选题，不要去过多论述一般项目成本管理的必要性，而应该找出目前房地产项目开发过程中与成本管理密切相关的普遍问题，作为出发点论述解决这些问题的价值。2 国内外研究现状作为一个毕业生，你的能力水平和眼界是有一定局限性的，也可以说你现在的课题研究是“站在巨人的肩膀上”，所以国内外研究现状是肯定要提前了解的，这样才能更好的指导自己的选题。再者，毕业论文或者设计最根本的要求是要有创新性，因此，针对选题，必须广泛查阅国内外相关的前沿文献，了解他人在这些问题上所做的工作和别人在这一领域研究的基本情况。熟悉了别人在这方面的研究情况，才不会在别人已经研究很多、很成熟的情况下，重复别人走过的路，而会站在别人研究的基础上，从事更高层次、更有价值的东西去研究。在开题报告的撰写中，【研究现状】部分应该明确指出国内外文献已经提出的观点、结论、解决方法和阶段性研究成果。相关文字表达可以这样写：“谁—利用什么方法—在哪个问题上—取得了什么进展”以及“该工作有何优劣”。另外，叙述完国内外研究现状之后，要评述上述文献研究成果的不足，寻找有待进一步研究的问题，从而确定选题研究的平台（起点）、研究的特色或突破点，提出作者的学位论文准备论证的观点或解决方法。在引述他人的工作成果时，一定要注明引用的出处（参考文献）。只有被引用了的文献才能出现在后面的参考文献当中。3 研究方案及研究路径研究方案是在选题的重要性和必要性确定之后，对选题研究的工作计划，初步规定了选题研究的方法、内容和路径，对整个选题研究工作的顺利开展起着非常关键的作用。一个好的研究方案，可以避免无从下手或进行一段时间后不知道下一步该干什么的情况，保证整个选题研究工作有条不紊地进行。研究方案水平的高低，是一个选题质量与水平的重要反映。 研究方法研究方法的选择应该建立在他人研究同类问题所采用的思路、方法、工具上，要分析别人思路的优缺点，然后提出自己的主张。研究方法要可行、具体，不要出现“定性与定量相结合”、“理论和案例研究相结合”等没有任何内涵的表述。研究方法包括：访谈、观察、文献调研、调查、案例分析、经验总结、实验、数值分析（仿真）、理论推导、比较研究等。研究可以采用其中一种方法或多种方法结合，并且提倡使用综合的研究方法。 研究内容选题明确之后，要确定可行的研究内容。研究内容一是根据研究目标来确定；二是从现状研究、归因研究、应用（方法）研究或对策研究几方面来确定。现状研究是基础；归因研究是为了寻找解决问题的突破口；应用（方法）研究或对策研究是研究的重点。研究内容的确定具体就是拟定论文的结构，可以按章节写，而且在每一节模块下用简单的几句话说明该模块要做的主要工作。确定研究内容容易出现的问题有：拟定研究内容太难、太多，在一年内完成不现实、风险大；拟定内容太容易、太少，看不出工作量，达不到硕士学位论文的要求；内容安排就像是工作总结；体现工作的核心内容不多；研究内容安排内在逻辑不连贯。 研究路径研究路径可以用“研究路径图”来说明。该研究路径图反映了研究工作展开的逻辑顺序。可以把“研究内容”看成是论文工作的工作分解结构，而研究路径图就是论文工作的网络图。4 研究过程可能遇到的困难和问题，解决的初步设想困难和问题是指在研究内容中的哪些问题、研究方法的应用哪些方面是困难和问题之处，要针对他人很少研究、突破不大、对解决问题有价值的研究内容提出来的，尽量不要说“时间不充足”、“基础不扎实”等自身原因产生的“困难和问题”。比如：研究中所用的研究理论、研究方法作者是否掌握、能有效运用；研究中所需的材料、资料、数据是否能获得等。解决的初步设想就是准备采取什么方法、手段和措施解决研究过程可能遇到的困难和问题5 参考文献参考文献表是文中引用的有具体文字来源的文献集合。为了反映论文的科学依据和作者尊重他人研究成果的严肃态度以及向读者提供有关信息的出处，应列出参考文献表。参考文献表中列出的一般应限于作者直接阅读过的、最主要的、发表在正式出版物上的文献。切记例举太多无用的参考书目。小tips：撰写开题报告的时候一定要频繁与导师交流。绝大多数毕业生都是第一次写开题报告，缺乏这方面的经验，难免会需要多次修改。有的毕业生可能会想，导师都已经那么忙了，就不要去打扰导师了。要知道，导师最不怕的就是你问他，最怕的反而是你不懂也不问他，自己闷着头写完了，到最后修修改改的，岂不是更麻烦，所以，一定要及时沟通，这样，也能在较短的时间里加强自己的分析与撰写能力，少走弯路。

在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。求关键路径的算法分析（1） 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径； （2） 只有缩短关键活动的工期才有可能缩短工期； （3） 若一个关键活动不在所有的关键路径上，减少它并不能减少工期； （4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。探寻关键路径AOE网用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。例如： 图1图1 是一个网。其中有9个事件v1，v2，…，v9；11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，v9 表示整个工程结束。V5表示活动，a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6天时间可以完成。AOE 网具有的性质只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。 只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。 表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。 2)最早发生时间和最晚发生时间的定义可以采取如下步骤求得关键活动： A、从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。 Ve(k)=max{ve(j) dut()} （ ） j ∈ T 其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。 如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。 表1B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间: vl(j)=min{vl(k)-dut()} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。 C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j)；最晚开始时间： l(i)=vl(k)-dut() 若某条弧满足 e(i)=l(i) ，则它是关键活动。 对于图1所示的 AOE 网，按以上步骤的计算结果见表1，可得到a1 , a4 , a7 , a8 , a10 , a11 是关键活动。AOE 网的关键路径 图2这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如图的AOE网中有二条关键路径，(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它们的路径长度都是16 。如图2所示：AOE网研究的问题（1） 完成整个工程至少需要多少时间； （2） 哪些活动是影响工程的关键。 1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。关键路径的几个术语（1） 关键路径 从源点到汇点的路径长度最长的路径叫关键路径。 （2） 活动开始的最早时间e(i) （3） 活动开始的最晚时间l(i) 定义e(i)=l(i)的活动叫关键活动。 （4） 事件开始的最早时间ve(i) （5） 事件开始的最晚时间vl(i) 设活动ai由弧(即从顶点j到k)表示，其持续时间记为dut(),则 e(i)=ve(j) l(i)=vl(k)-dut() (6_6_1) 求ve(i)和vl(j)分两步： · 从ve(1)=0开始向前递推 ve(j)=Max{ ve(i)+dut() } (6_6_2) T, 2<=j<=n 其中，T是所有以j为弧头的弧的集合。 · 从vl(n)=ve(n)开始向后递推 vl(i)=Min{ vl(j)-dut() } (6_6_3) S, 1<=i<=n-1 其中，S是所有以i为弧尾的弧的集合。 两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。 4、 求关键路径的算法 (1) 输入e条弧，建立AOE网的存储结构。 (2) 从源点v1出发，令ve(1)=0,求 ve(j) 2<=j<=n。 (3) 从汇点vn出发，令vl(n)=ve(n),求 vl(i) 1<=i<=n-1。 (4) 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。 求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。 Status ToplogicalSort(ALGraph G,stack &T){ FindInDegree(G,indegree); InitStack(S);count=0; ve[0..]=0; while(!StackEmpty(S)) { Pop(S,j);Push(T,j); ++count; for(p=[j].firstarc;p;p=p->nextarc) {k=p>adjvex; if(--indegree[k]==0) Push(S,k); if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); } } if(count<) return ERROR; else return OK; } status CriticalPath(ALGraph G){ if(!ToplogicalOrder(G,T)) return ERROR; vl[0..]=ve[0..]; while(!StackEmpty(T)) for(Pop(T,j),p=[j].firstarc;p;p=p->nextarc) {k=p>adjvex; dut=*(p->info); if(vl[k]-dutnextarc) {k=p>adjvex; dut=*(p->info); ee=ve[j]; el=vl[k]; tag=(ee==el)?’*’:’’; printf(j,kdut,ee,el,tag); } }