********5.4最短路径,关键路径与着色带权图最短路径与Dijkstra标号法项目网络图与关键路径着色问题*最短路径带权图G=V,E,w,其中w:E?R.(权函数)?e?E,w(e)称作e的权.e=(vi,vj),记w(e)=wij.若vi,vj不相邻,记wij=?.通路L的权:L的所有边的权之和,记作w(L).u和v之间的最短路径:u和v之间权最小的通路.例L1=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.*标号法(E.W.Dijkstra,1959)设带权图G=V,E,w,其中?e?E,w(e)?0.设V={v1,v2,?,vn},求v1到其余各顶点的最短路径1.（初始步）令l1?0,p1??,lj?+?,pj??,j=2,3,?,n,P={v1},T=V-{v1},k?1,t?1./?表示空2.（更新长度）对所有的vj?T且(vk,vj)?E令l?min{lj,lk+wkj},若l=lk+wkj,则令lj?l,pj?vk.3.求li=min{lj|vj?Tt}.（当前最短）令P?P?{vi},T?T-{vi},k?i.4.令t?t+1,若tn,则转2.*Dijkstra标号法实例例求v0到v5的最短路径tv0v1v2v3v4v51(0,?)(+?,?)(+?,?)(+?,?)(+?,?)(+?,?)2(1,v0)(4,v0)(+?,?)(+?,?)(+?,?)3(3,v1)(8,v1)(6,v1)(+?,?)4(8,v1)(4,v2)(+?,?)5(7,v4)(10,v4)6(9,v3)v0到v5的最短路径:v0v1v2v4v3v5,d(v0,v5)=9*******项目网络图项目网络图（AOE-网）:带权有向无环图，表示项目活动之间前后顺序一致.边表示活动,边权是活动的完成时间,顶点表示事件(即项目的开始和结束、活动的开始和结束).要求:(1)有一个始点(入度为0)和一个终点(出度为0).(2)任两点间只有一边.(3)没有回路.(4)每边始点的编号小于终点的编号.A引入虚活动ABBCCX待研究的问题是：
（1）项目完成至少要多少时间
（2）影响项目进度的关键活动是哪些例子：*活动ABCDEFGHIJKL--紧前活动???AAA,BA,BA,BC,HD,FE,IG,KJ,L时间(天)123434424611对应顶点①②③④⑦⑤⑥⑧41235678ABCDEFGHIJKL1234