有P标号的顶点数多一个,这样,至多经过点数-1步,就可以求出从v1 到各点的最短路。Р最短路算法—Dijkstra标号法Р步骤:?①给vs 以P标号0,其它点给T标号+∞;?②从刚得到P标号的点vk出发,按下式修改与其相邻的所有具有T标号的点的标号;Р③从所有具有T标号点中选取一个最小值,将其改为P标号,然后重复步骤②,直至所有点都得到P标号。РDijkstra(狄克斯拉)标号法?具体实现Р从起点vs开始,逐步给每个结点vj标号[dj,vi],其中dj为起点vs到vj的最短距离,vi为该最短路线上的前一节点。Р[1, v1]Р[0, v1]Р(1) 给起点v1标号[0, v1]Р(3) 考虑所有这样的边[vi , vj],其中vi∈VA, vj∈VB,挑选其中与起点v1距离最短(min{di+cij})的vj,对vj进行标号Р(4) 重复(2)、( 3),直至终点vn标上号[dn, vi],则d1n即为v1→ vn的最短距离,反向追踪可求出最短路。Р(2) 把顶点集V分成РVA:已标号点集РVB:未标号点集Р10Рv2Рv1Рv3Рv4Рv5Рv6Рv7Рv9Рv8Р1Р6Р3Р2Р2Р2Р2Р6Р6Р1Р3Р3Р10Р4Р4Р[1, v1]Р[0, v1]Р10Рv2Рv1Рv3Рv4Рv5Рv6Рv7Рv9Рv8Р1Р6Р3Р2Р2Р2Р2Р6Р6Р1Р3Р3Р10Р4Р4Р[3, v1]Р[0, v1]Р[1, v1]Р[3, v1]Р[5, v3]Р10Рv2Рv1Рv3Рv4Рv5Рv6Рv7Рv9Рv8Р1Р6Р3Р2Р2Р2Р2Р6Р6Р1Р3Р3Р10Р4Р4Р[0, v1]Р[1, v1]Р[3, v1]Р[5, v3]Р[6, v2]Р10Рv2Рv1Рv3Рv4Рv5Рv6Рv7Рv9Рv8Р1Р6Р3Р2Р2Р2Р2Р6Р6Р1Р3Р3Р10Р4Р4
全文预览
