Page 212 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

enddata
n=@size(cities)； ! 城市的个数；
min=@sum(roads：w*x)；

@for(cities(i)|i #ne#1 #and# i #ne#n：
@sum(roads(i，j)：x(i，j))=@sum(roads(j，i)：x(j，i)))；
@sum(roads(i，j)|i #eq#1：x(i，j))=1；
@sum(roads(i，j)|j #eq#n：x(i，j))=1；
end

（三）每对顶点之间的最短路径
计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。具体方

法是：每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的
最短路径，反复执行 n � 1 次这样的操作，就可得到从每一个顶点到其他顶点
的最短路径。这种算法的时间复杂度为 O(n3) 。第二种解决这一问题的方法是由
Floyd R W 出的算法，称之为 Floyd 算法。
假设图 G 权的邻接矩阵为 A0 ，

来存放各边长度，其中：

Floyd 算法的基本思想是：递推产生一个矩阵序列 A0 ， A1，…， Ak ，…L，
An ，其中 Ak (i， j) 表示从顶点 vi 到顶点 v j 的路径上所经过的顶点序号不大于

k 的最短路径长度。
计算时用迭代公式：
Ak (i， j) = min(Ak － 1(i， j)， Ak － 1(i，k) ＋ Ak － 1(k， j))
k 是迭代次数，i， j，k=1，2，…，n。

202