毕业论文：Dijkstra最短路径算法的优化和改进

30Р100Р2Р3Р0Р10Р50Р30Р90Р3Р2Р0Р10Р50Р30Р60Р4Р4Р0Р10Р50Р30Р60Р2.2.2 应用Р给定简单定简单无向图,指定一顶点为起点,对于任意∈且≠,求到的最短路径的长度.Р例:某单位使用一台设备,在每年年初,企业部门领导都要决定是购置新设备代替原来的旧设备,还是继续使用旧设备.若购置新设备,需要支付一定的购置费用;若继续使用旧设备,需支付一定的维修费用.设该种设备在每年年初的价格(万元)见表2-2使用的不同时间(年)的设备所需要的维修费用(万元)见表2-3.问如何制定一个五年之内的设备更新计划,使总费用最少.Р表2-2 价格表Р第年Р1Р2Р3Р4Р5Р价格Р11Р12Р13Р12Р13Р表2-3 维修费用表Р使用年数Р维修费用Р5Р6Р8Р11Р18Р16Р17Р18Р59Р41Р42Р17Р18Р23Р32Р24Р23Р30Р22Р图2-2 赋权有向网络图Р用点表示“第i年年初购进一台新设备”这种状态,=1,2,…,5,用表示第五年底的状态.对于每个=1,2,…,5从到,…;各画一条弧,弧(,)表示在第i年年初购进一台设备一直使用到第年年初(即第年底).每条弧的权可按已知的数据计算出来,例如(,)表示第一年年初购进一台新设备,需支付11万元,一直使用到第三年年底,需维修费(5+6+8)万元=19万元,故其上的权为30.Р这样就可以得到一个赋权有向网络,如图2-3所示,所求问题等价于需找从到的最短路问题.用Dijkstra算法求解,最优解为(,,),即分别在第1、4年年初购买一台新设备,总费用为53万元.上述为Dijkstra最基本的求解路径的方法.Р2.3 Dijkstra算法与其他主流算法的比较Р2.3.1 搜索速度比较Р对5张图分别采用Dijkstra算法、算法、遗传算法进行路径规划,他们各自花费的时间如表2-4所示.