Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。
Dijkstra算法基本步骤③： 令：s??vi?,i?1,s??v2,v3,?,vn? 并令：?W?v1??0T?vj???,vj?s??_
1、对vj?s，求minT?vj?,W?vi??wij?T?vj?。 2、求minTvjvj?s??????得T?v?，使T?v?=min?T?v??
kkjvj?s令W?vk??T?vk?
3、若vk?vn则已找到v1到vn的最短路距离W?vk?，否则令i?k从s中删去vi转1
这样经过有限次迭代则可以求出v1到vn的最短路线，可以用一个流程图来表示：
?
第一步 先取W?v1??0意即v1到v1的距离为0,而T?vj?是对T?vj?所赋的初
值。
第二步 利用W?v1?已知,根据minT?vj?,W?vi??wij对T?vj?进行修正。 第三步 对所有修正后的T?vj?求出其最小者T?vk?。其对应的点vk是v1所能一步到达的点vj中最近的一个,由于所有W?u??0。因此任何从其它点vj中转而到达vk的通路上的距离都大于v1直接到vk的距离T?vk?,因此T?vk?就是v1到vk的最短距离,所以在算法中令W?vk??T?vk?并从s中删去vk,若k=n则
W?vk??W?vn?就是v1到vn的最短路线,计算结束。否则令vi?vk回到第二步,继续
??运算,直到k=n为止。
这样每一次迭代,得到v1到一点vk的最短距离,重复上述过程直到vk?vn。 Floyd算法的基本原理和实现方法为:如果一个矩阵D???dij??其中dij?0表示i与
j间的距离,若i与j间无路可通,则dij为无穷大。i与j间的最短距离存在经过i与检查dij与j间的k和不经过k两种情况,所以可以令k?1,2,3,?,n,n(n为节点数)。
dik?dkj的值,在此,dik与dkj分别为目前所知的i到k与k到j的最短距离,因
此,dik?dkj就是i到j经过k的最短距离。所以,若有dij?dik?dkj,就表示从i出发经k再到j的距离要比原来的i到j距离短,自然把i到j的dij重写成dik?dkj。每当一个k搜索完,dij就是目前i到j的最短距离。重复这一过程,最后当查完所有k时,dij就为i到j的最短距离。
运用迪杰斯特拉方法，通过Lingo软件求解得到如下数据：（程序见附录）
通过检验求得结果相同，因此可以证明以上答案； 5.2针对问题二的模型建立与求解
5.2.1模型分析
很明显运输公司分别要对10个客户供货，必须访问每个客户，但问题要求我们建立相应模型寻找一条尽可能短的行车路线，首先不考虑送货员把10个客户所需的货送完货后不返回提货点的情形，利用求最小生成树的prim算法结合题中所给的邻接矩阵，很快可以得到以下一棵最小生成树：
1 5 7 6 3 2 10 9 8 4 以上路线的总行程为175公里，充分利用问题一所建的模型(1),很快就可以求得V2（客户2）返回V1（提货点）的最线路是V2?V1行程50公里(注:代用模型(1)时,需先将题中的邻接矩阵的第一行与第二行交换,第一列与第二列交换后参照附录[1]的代码可求解)，我们有理由相信这样构成的回路实际上也是最短回路：
1 5 7 6 3
2 109 8 4
该回路可描述为：
V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1
总行程为225公里。这种寻路方法并不比其他方法差而且它的速度也很快，只是它局限于顶点数较少的情形，一旦顶点数扩大实现起来难度就会大大提高，而且它的不易推广，因此我们有必要对此问题深入研究，进而建立起一个数学模型以适应顶点数变化，使它能够具有较好的推广性，应用到现实生活中去来实现以不变应万变的现象。 5.2.2模型建立与求解
可建立问题的模型(2)为：
1010目标函数:minZ???Cij?Xiji?1j?1?10??Xij?1?i?1,2,?,10?j?1?10?X?1?j?1,2,?,10?ij??i?1?X?0或1?0,1变量? ?条件:?ij?整型变量??Xij?N?ui?uj?n?Xij?n?1??2?i?j?n??ui?0???i?1,2,?,10??
同样借助数学软件求解可得结果：
从中可以找出一条较为理想的回路是：
V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1
可见按此模型求解的结果与采用prim算法求解的结果是一样的。 5.2.3模型检验
在程序设计中，有时会用到由若干个有限数据元素组成的集合，程序中某个变量取值仅限于集合中的元素。此时，可将这些数据集合定义为枚举类型。因此，枚举类型是某类数据可能取值的集合：下面为运用枚举法求解所得到的数据； 一种方式；
1 5 7 6 3 2 109 8 4
第二种方式：
1 2 3 4 5 10 9 8 7 6 通过总路程对比可知，两种方法所得数据相同，因此可以证明此结论正确；
5.3针对问题三的模型建立与求解
5.3.1模型的猜想
用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短，我们假设每个客户的货物都由同一辆货车提供，这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。实际 上这样的两条回路是存在的：由题二得到了一条哈密顿回路
V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1
可根据货物需求量的大小将其分为前后两部分，并将之分别构成回路。（注：由于提货点在客户1所在的位置，故不必考虑为客户1送货的情况。） （1）由此思想建立以下模型
Step1：根据以下模型获得一个值k；
Step2：依k的取值分两条路径：
L1:V1?VGet?N1????VGet?Nk?L2:VGet?NK?1??VGet?NK?2????V1
Step3：利用模型(1)分别求得VGet?Nk?到V1的最短路径：VGet?NK????V1 以及
V1到VGet?NK?1?的最短路径：V1???VGet?NK?1?
Step4：从而获取两辆货车的路线如下表： 车号 路线 一号车 V1?VGet?N1????VGet?Nk????V1 二号车 V1???VGet?NK?1??VGet?NK?2????V1 据上描述可建立模型；
目标:maxk?kU?Ni??50???1条件:?ki??1??U?Ni??50??i?1
?k?1,2,?,9?