第2讲 最短路.ppt

最短路问题:双标号解法标号[i,j]的含义:第一标号i表示从始点到当前顶点的最短路线长度为i。第二标号j表示在从始点到当前顶点的最短路线上,当前顶点的前继顶点编号为j。豺跋冲外***蛮幽考绢潦腋底值冲蹈证择棒杏眉租糕谦膳悄地垒蚂倘捏娶僻第2讲最短路第2讲最短路最短路问题例:有向图v1v3v2v5v6v4250400150100[0][250,1]275100200150300[350,2][500,3][600,4][700,4]纳埃拘妙蒋庐彼榜卿佃趁然看杜百墅懂樊驰癌泳构房魏肋祸屿汁墟券僵戌第2讲最短路第2讲最短路Dijstra最短路问题解法在施行过程中,对于每个顶点Vj都要赋予一个标号,这分为固定标号(P标号)和临时标号(T标号)两类,含义如下:P标号:从起点到当前顶点的最短路长。T标号:从起点到当前顶点的最短路线长度的上界。注:每个顶点的标号只能够是P和T二者之一。如果为T标号,则有待修改,而一旦成为P标号,则固定不变了。孟瞩厚嘻衰谊绰敞刘致艰衬鼎铰醉挽南吴掘霸永革詹八稍淌此铃镭痛徘诛第2讲最短路第2讲最短路具体标号过程开始先给起点V1标上P标号0,给其余顶点标上T标号∞,然后检查与V1相邻的一切顶点Vj,选取到起点距离最小者,将其顶点T标号修改为P标号;以后每次检查刚得到P标号的顶点,检查与它相邻的一切顶点,同样从中选取到起点距离最小者,将其顶点T标号修改为P标号;由于每次都将一个T标号修改为P标号,总共n个顶点,故最多需要n-1次就可以将终点改为P标号魁前讨策碧取妄沧噎扰誓像桃勉芯刁送弧樱磷讼确余浩谍她溅立告虏陈雁第2讲最短路第2讲最短路特别提示Dijstra最短路解法对于具有负权的网络有可能失效;这种解法也可以采用图上标注的双标号方式,每一顶点的第一标号表明它的前继顶点,第二标号表明从起点到当前顶点的最短路线长度。标号过程正是将T标号顶点逐步修改为P标号顶点的过程。肩脊帅田摔贪斡郑邯骑莎泡被挟乒目肾辕峻台火唤竞哼仙札孝舶高盖褐荷第2讲最短路第2讲最短路求最短路例:图上标注法v1v3v2v5v6v45227(0)(v1,5)1367(v1,2)(v2,7)(v6,7)(v3,6)v7462(v5,10)鸡痕瞧套尤蔓鸥笼濒趟到甩播昏奠拔九膨耘腋旬柒姿矾电遁萄恕康圃代哩第2讲最短路第2讲最短路最短路模型的应用渡河问题:摆渡人需要将狼,羊和卷心菜带过河去,由于船小,每次只能够载一样东西,狼和羊,羊和卷心菜不能够在无人监视的情况下放在一起,您将如何安排渡河?平均分酒问题:有一只8升酒壶装满酒,另外有二只空酒壶分别为5升和3升,将酒平分的最简单方法是什么?思考:应该如何建立最短路模型求解?拍鸟褥屎客齐叶魂杯经窖能谚浙霞秀